个人练习

6. The Shortest Path in Nya Graph

题意：设一个图为一个具有层的无向图，可以从 $x$ 层的任一点移动到 $x+1$ 层的任意点，花费 $c$ ，在同一层移动不需要花费。另外还有 $m$ 条额外的边，花费为 $w$ ，计算点1到点 $n$ 的最短距离。

一个需要增点建图的题。

增点有很多方法，给出一种增点建图方法如下：相邻两层中间设两个节点，下层到上层用一个点，下层点汇聚到增点花费为 $c$ ，增点又连向上层所有点花费为0；上层到下层同理。

#include<bits/stdc++.h>
using namespace std;

const int N=300006;
int n,m,c;
vector<pair<int,int> >g[N];
vector<int>lay[N];
int dis[N];
int vis[N];

void solve()
{
    memset(vis,0,sizeof(vis));
    cin>>n>>m>>c;

    for(int i=1;i<=n*2+1;i++)vis[i]=0,g[i].clear(),lay[i].clear();

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        lay[x].push_back(i);
    }

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }

    // for(auto i:cnt)
    // {
    //     for(auto j:lay[i])
    //     {
    //         g[j].push_back({i+n,0});
    //         g[i+n].push_back({j,0});
    //     }
    // }

    // sort(cnt.begin(),cnt.end());
    // for(int i=0;i<cnt.size()-1;i++)
    // {
    //     if(cnt[i]+1==cnt[i+1])
    //     {
    //         g[cnt[i]+n].push_back({cnt[i]+n+1,c});
    //         g[cnt[i]+n+1].push_back({cnt[i]+n,c});
    //     }
    // }

    int node=n+1;
    for(int i=1;i<n;i++)
    {
        if(!lay[i].empty()&&!lay[i+1].empty())
        {
            for(int j=0;j<lay[i].size();j++)
            {
                int u=lay[i][j];
                g[u].push_back({node,c});
            } 
            for(int j=0;j<lay[i+1].size();j++)
            {
                int v=lay[i+1][j];
                g[node].push_back({v,0});
            }
            node++; 
        }
    }

    for(int i=n;i>1;i--)
    {
        if(!lay[i].empty()&&!lay[i-1].empty())
        {
            for(int j=0;j<lay[i].size();j++)
            {
                int u=lay[i][j];
                g[u].push_back({node,c});
            } 
            for(int j=0;j<lay[i-1].size();j++)
            {
                int v=lay[i-1][j];
                g[node].push_back({v,0});
            }
            node++; 
        } 
    }


    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue<pair<int,int> > q;
    q.push({0,1});

    while(q.size())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;

        for(auto [v,w]:g[u])
        {
            if(vis[v])continue;

            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({-dis[v],v});
            }
        }
    }

    if(dis[n]==0x3f3f3f3f)cout<<"-1\n";
    else cout<<dis[n]<<endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)cout<<"Case #"<<i<<": ",solve();
    return 0;
}

最短路，增点

11. How Many Answers Are Wrong

题意：一共有 $n$ 个数，给出 $m$ 个条件形如 $i,j,s$ 表示 $a_i+a_{i+1}+…+a_j=s$ 。判断有多少个条件与之前的条件矛盾。

前置知识：扩展域与边带权并查集

每个条件可简化为 $sum[j]-sum[i-1]=s$ ，可用带边权的并查集判断矛盾。

在合并节点时，可画图理解：$fa[fy]=fx,\ d[fy]=s+d[x]-d[y]$ 。

#include<bits/stdc++.h>
using namespace std;

int n,m,ans;
int fa[200005];
int d[200005];

int getfa(int x)
{
    if(x==fa[x])return x;
    int rt=getfa(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=rt;
}

int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<=n;i++)fa[i]=i,d[i]=0;
        ans=0;

        for(int i=1;i<=m;i++)
        {
            int x,y,w;
            cin>>x>>y>>w;
            x--;

            int fx=getfa(x);
            int fy=getfa(y);

            if(fx==fy)
            {
                if(d[y]-d[x]!=w)ans++;
            }
            else
            {
                fa[fy]=fx;
                d[fy]=w+d[x]-d[y];
            }
        }
        cout<<ans;
    }
    return 0;
}

并查集

13. Minimum spanning tree for each edge

题意：给一个图，求出包含每一条边的最小生成树大小。

前置知识：直径与最近公共祖先

注意到一个很重要的性质：非严格次小生成树由最小生成树加上一条边并删去形成环中的一条边生成。

那么确定包含某一条边时，若这条边在最小生成树中，那么答案就是最小生成树；若这条边不在，那么就需要在最小生成树加上这条边之后构成的环中删去一条最大的边，构成包含这条边的最小生成树。

那么最后的问题就是如何求出构成的环中的最大边。假设新接入的边为 $u\rightarrow v$ ，那么需要找到 $u\rightarrow lca(u,v)$ 以及 $v\rightarrow lca(u,v)$ 路径上的最大值。最大值可以在 $lca$ 预处理中完成，在预处理 $fa[x][i]$ 时处理出 $mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1])$ 。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+5;

int n,m;
int t;

struct bian
{
    int u,v,w,id;
}edg[N*2],edg1[N*2];

int cnt,hed[N],nxt[N*2],to[N*2],val[N*2];

int fa[N][20],mx[N][20];
int ft[N];
int d[N];
int ans[N];
int mnd;

bool cmp(bian x,bian y)
{
    return x.w<y.w;
}

int getfa(int x)
{
    return ft[x] = x==ft[x]?x:getfa(ft[x]);
}

void add(int x,int y,int w)
{
    to[++cnt]=y;
    val[cnt]=w;
    nxt[cnt]=hed[x];
    hed[x]=cnt;
}

void bfs()
{
    queue<int>q;
    d[1]=1;
    q.push(1);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=hed[u];i;i=nxt[i])
        {
            int v=to[i];
            int w=val[i];
            if(d[v])continue;
            d[v]=d[u]+1;
            fa[v][0]=u;
            mx[v][0]=w;
            for(int j=1;j<=t;j++)
            {
                fa[v][j]=fa[fa[v][j-1]][j-1];
                mx[v][j]=max(mx[v][j-1],mx[fa[v][j-1]][j-1]);

            }
            q.push(v);
        }
    }
}

int lca(int x,int y)
{
    int tmp=0;
    if(d[x]>d[y])swap(x,y);

    for(int i=t;i>=0;i--)
    {
        if(d[fa[y][i]]>=d[x])
        {
            tmp=max(tmp,mx[y][i]);
            y=fa[y][i];
        }
    }
    if(x==y)return tmp;
    for(int i=t;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            tmp=max(tmp,mx[x][i]);
            tmp=max(tmp,mx[y][i]);
            x=fa[x][i],y=fa[y][i];
        }
    }
    return max(max(tmp,mx[x][0]),mx[y][0]);
}

signed main()
{
    cin>>n>>m;
    t=(int)(log(n)/log(2))+1;

    for(int i=1;i<=m;i++)
    {
        cin>>edg[i].u>>edg[i].v>>edg[i].w;
        edg[i].id=i;
        edg1[i].u=edg[i].u;
        edg1[i].v=edg[i].v;
        edg1[i].w=edg[i].w;
    }

    for(int i=1;i<=n;i++)ft[i]=i;

    sort(edg+1,edg+m+1,cmp);

    for(int i=1;i<=m;i++)
    {
        int fx=getfa(edg[i].u);
        int fy=getfa(edg[i].v);
        if(fx==fy)continue;
        mnd+=edg[i].w;
        ans[edg[i].id]=-1;
        ft[fy]=fx;
        add(edg[i].u,edg[i].v,edg[i].w);
        add(edg[i].v,edg[i].u,edg[i].w);
    }

    bfs();

    for(int i=1;i<=m;i++)
    {
        int id=edg[i].id;
        if(ans[id]==-1)
        {
            ans[id]=mnd;
            continue;
        }
        
        int tmp=lca(edg1[id].u,edg1[id].v);
        ans[id]=mnd-tmp+edg1[id].w;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    return 0;
}

最小生成树，最近公共祖先

14. Diameter set

题意：给定一棵树，求有多少种集合，满足集合内任两点的距离都是直径。

由直径重要性质知在无负权边的树上，所有直径的中点重合。那么考虑先找出一条直径，确定中点。

若中点为节点 $p$ ，那么统计 $p$ 的每个儿子有多少条满足长度要求的链，最后答案为：

$$
(tot_1+1)\times (tot_2+1)\times …\times (tot_n+1)-(tot_1+tot_2+…+tot_n+1)
$$

若中点在一条边 $(u,v)$ 上，那么答案为 $u,v$ 子树中深度为 $diameter/2$ 的点的数量之积。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+5;
const int mod=998244353;
int n;
int cnt,hed[N*2],nxt[N*2],to[N*2];
int d[N],f[N];

int dmx,vt,zj,tot,bz;

void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=hed[x];
    hed[x]=cnt;
}

void dfs(int u,int fa)
{
    for(int i=hed[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)continue;
        d[v]=d[u]+1;
        f[v]=u;

        if(d[v]>dmx)
        {
            dmx=d[v];
            vt=v;
        }
        dfs(v,u);
        
    }
}

void dfs2(int u,int fa,int st)
{
    if(st==bz)tot++;
    for(int i=hed[u];i;i=nxt[i])
    {
        if(to[i]==fa)continue;
        dfs2(to[i],u,st+1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }

    dmx=0;
    dfs(1,0);
    int st=vt;

    dmx=0;memset(d,0,sizeof(d));
    dfs(vt,0);
    int ed=vt;
    
    zj=dmx;

    // cout<<zj<<endl;

    // for(int i=vt;i!=st;i=f[i])cout<<i<<" ";cout<<st<<endl;

    if(zj%2==0)
    {
        int cnt=0;
        int bk;
        for(int i=ed;i;i=f[i])
        {
            cnt++;
            if(cnt==zj/2+1)
            {
                bk=i;
                break;
            }
        }
        // cout<<bk<<endl;
        int ans=1;
        bz=zj/2-1;
        for(int i=hed[bk];i;i=nxt[i])
        {
            int v=to[i];
            tot=0;
            dfs2(v,bk,0);
            ans=(ans*(tot+1))%mod;
        }
        tot=0;
        bz++;
        dfs2(bk,0,0);
        ans=(ans+mod-(tot+1))%mod;
        cout<<ans;
    }

    else
    {
        int cnt=0;
        int bk1,bk2;
        for(int i=ed;i;i=f[i])
        {
            cnt++;
            if(cnt==zj/2+1)
            {
                bk1=i;bk2=f[i];
                break;
            }
        }

        // cout<<bk1<<" "<<bk2<<endl<<endl;

        bz=zj/2;

        int ans=1;
        tot=0;
        dfs2(bk1,bk2,0);
        // cout<<tot<<endl;
        ans=ans*tot%mod;

        tot=0;
        dfs2(bk2,bk1,0);
        // cout<<tot<<endl;
        ans=ans*tot%mod;
        cout<<ans;
    }


}

树的直径

15. Information Graph

题意：有 $n$ 个人，$m$ 个事件，若输入格式为 $1\ x\ y$ 则表示 $x$ 成为了 $y$ 的上司，若为 $2\ x$ 则表示从 $x$ 开始开始上传从1开始编号的一份文件。每次询问某一个人有没有读过某一号文件。

首先用并查集简单记录员工和最高上司的关系，每有一个上司关系就连一条边。对于每一份文件，只需要存储文件开始的位置和结束的位置。最后查询时，可用 $lca$ 查询：若文件起始位置为 $u,v$ ，查询 $p$ ，那么一定有 $lca(u,p)=p\ and\ lca(p,v)=v$ 或者 $lca(u,p)=u\ and\ lca(p,v)=p$ 。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m,t;
int cnt,hed[N*2],nxt[N*2],to[N*2];

int ft[N];
int fa[N][30];

int d[N];

int tot;
int c;
struct shit
{
    int em,num;
}q[N];

pair<int,int>mp[N];

void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=hed[x];
    hed[x]=cnt;
}

int getfa(int x)
{
    return ft[x] = x==ft[x]?x:getfa(ft[x]);
}

void merge(int s,int f)
{
    s=getfa(s);
    f=getfa(f);
    ft[s]=f;
}

void bfs(int st)
{
    queue<int>pq;
    d[st]=1;
    pq.push(st);
    while(pq.size())
    {
        int u=pq.front();
        pq.pop();
        for(int i=hed[u];i;i=nxt[i])
        {
            int v=to[i];
            if(d[v])continue;
            d[v]=d[u]+1;
            fa[v][0]=u;
            for(int j=1;j<=t;j++)fa[v][j]=fa[fa[v][j-1]][j-1];
            pq.push(v);
        }
    }
}

int lca(int x,int y)
{
    if(d[x]>d[y])swap(x,y);
    for(int i=t;i>=0;i--)if(d[fa[y][i]]>=d[x])y=fa[y][i];
    if(x==y)return x;
    for(int i=t;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main()
{
    cin>>n>>m;

    t=(int)(log(n)/log(2))+1;

    for(int i=1;i<=n;i++)ft[i]=i;
    for(int i=1;i<=m;i++)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y;
            cin>>x>>y;
            add(x,y);
            add(y,x);
            merge(x,y);
        }
        if(op==2)
        {
            int x;
            cin>>x;
            int fx=getfa(x);
            mp[++tot].first=x,mp[tot].second=fx;
        }
        if(op==3)
        {
            cin>>q[++c].em>>q[c].num;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(!d[i])bfs(i);
    }

    // cout<<"lca(5,6)="<<lca(5,6)<<endl;
    // cout<<d[5]<<" "<<d[6]<<endl;
    for(int i=1;i<=c;i++)
    {
        int em=q[i].em,num=q[i].num;
        int x=mp[num].first,fx=mp[num].second;

        // cout<<em<<" "<<num<<" "<<x<<" "<<fx<<endl;

        if(getfa(ft[em]) != getfa(ft[x]))cout<<"NO\n";
        else
        {
            // cout<<lca(x,em)<<" "<<lca(em,fx)<<endl;
            if(lca(x,em)==em && lca(em,fx)==fx || lca(x,em)==x && lca(em,fx)==em)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }

    return 0;
}

并查集，最近公共祖先

16. Lazy Running

题意：有四个点围成一圈，从2号点出发，最后要回到2号点。求至少路程为 $S$ 时，走过的最短路程。

前置知识：同余最短路

在到达2号点时，可以通过走无数次的 $d=2\times min(w(2,1),w(2,3))$ 刷步数的同时回到2号点，那么将 $d$ 作为模数，处理到达2号点并且在模 $d$ 意义下达到的步数时走的最短步数，最后答案即是 $min(dis[x]+d\times t)$ 。

在求最短路时 $dis$ 数组开两维，另一位存到达该点且模值为 $x$ 的最短路。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int k,a,b,c,d;
int f[5][100005];
int mod;
vector<pair<int,int> > g[5];

void dij()
{
    memset(f,0x3f,sizeof(f));
    f[2][0]=0;
    priority_queue<pair<int,int> > q;
    q.push({0,2});

    while(q.size())
    {
        int u=q.top().second;
        int w=-q.top().first;
        q.pop();

        if(w>f[u][w%mod])continue;

        for(auto i:g[u])
        {
            int v=i.first;
            int tmp=i.second;
            if(f[v][(tmp+w)%mod] > tmp+w)
            {
                f[v][(tmp+w)%mod]=tmp+w;
                q.push({-(tmp+w),v});
            }
        }
    }
}

void solve()
{
    
    cin>>k>>a>>b>>c>>d;
    
    for(int i=1;i<=4;i++)g[i].clear();

    g[1].push_back({2,a});
    g[2].push_back({1,a});
    g[2].push_back({3,b});
    g[3].push_back({2,b});
    g[3].push_back({4,c});
    g[4].push_back({3,c});
    g[4].push_back({1,d});
    g[1].push_back({4,d});

    mod=min(a,b);
    mod*=2;
    dij();


    int ans=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<mod;i++)
    {
        if(f[2][i]>k)ans=min(ans,f[2][i]);
        else
        {
            int t=(k-f[2][i]-1)/mod+1;
            int tmp=f[2][i]+t*mod;
            ans=min(ans,tmp);
        }
    }
    cout<<ans<<endl;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
}