ZR 集训 Day25 – 基础图论

ooliver 发布于 2026-08-10 354 次阅读 OI

AI 摘要

二进制分组、缩点、最小生成树——今天的图论题看似套路，实则暗藏玄机。台风吹来模拟赛，却吹不走思维的火花：最短路、最长链、概率并查集，都是转化艺术的极致。

前言

昨天通知今天有台风，所以今天上午改成了神秘模拟赛，题目啥的放最后吧。

P5304 [GXOI/GZOI2019] 旅行者

考虑二进制分组，即枚举 $k$ 个关键点的编号的二进制位，将 $0$、$1$ 分成两个集合，用一个超级源点连向一个集合、用一个超级汇点连向另一个集合，跑最短路即可。由于最终的答案的点对一定有一位上是不一样的，所以这个做法正确性显然。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1e5+5;

struct graph{
    int n;
    vector<pii> g[N];
    void init(int x){
        n=x;
        for(int i=1;i<=n;i++) g[i].clear();
    }
    void add(int u,int v,int w){
        g[u].push_back({v,w});
    }
    int dij(int s,int t){
        vector<int> dis(n+1,1e18),vis(n+1,0);
        priority_queue<pii> q;
        q.push({0,s});
        dis[s]=0;
        while(q.size()){
            auto[d,u]=q.top();
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto[v,w]:g[u]){
                if(!vis[v]&&dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    q.push({-dis[v],v});
                }
            }
        }
        return dis[t];
    }
}g;

void solve(){
    int n,m,k,ans=1e18;
    cin>>n>>m>>k;
    vector<int> d(k+1),u(m+1),v(m+1),w(m+1);
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=k;i++) cin>>d[i];
    for(int j=0;j<=19;j++){
        g.init(n+2);
        for(int i=1;i<=m;i++) g.add(u[i],v[i],w[i]);
        for(int i=1;i<=k;i++){
            if((d[i]>>j)&1) g.add(n+1,d[i],0);
            else g.add(d[i],n+2,0);
        }
        ans=min(ans,g.dij(n+1,n+2));
        g.init(n+2);
        for(int i=1;i<=m;i++) g.add(u[i],v[i],w[i]);
        for(int i=1;i<=k;i++){
            if((d[i]>>j)&1) g.add(d[i],n+1,0);
            else g.add(n+2,d[i],0);
        }
        ans=min(ans,g.dij(n+2,n+1));
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

P1262 [POI 1996 R3] 间谍网络

对拥有证据这个关系建边，形成一个有向图。对于图中的环，取点权最小的即可，可以考虑缩点成有向无环图，这样入度为 $0$ 的点即无法控制的点，需要收买。

代码：

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

const int N=1e5+5;
int n,m,p,idx,sum,ans;
int xu[N],xv[N],wis[N],mn[N],in[N];
int dfn[N],low[N],tag[N],scc[N];
stack<int> st;
vector<int> g[N];

void tj(int u){
    low[u]=dfn[u]=++idx,tag[u]=1;
    st.push(u);
    for(int v:g[u]){
        if(!dfn[v]){ 
            tj(v);
            low[u]=min(low[u],low[v]);
        }
        else if(tag[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        sum++;
        while(st.size()){
            int x=st.top();
            st.pop();
            scc[x]=sum,tag[x]=0,mn[sum]=min(mn[sum],wis[x]);
            if(x==u) break;
        }
    }
}

signed main(){
    scanf("%d%d",&n,&p);
    fill(wis+1,wis+1+n,1e9);
    fill(mn+1,mn+1+n,1e9);
    for(int i=1,id,w;i<=p;i++){
        scanf("%d%d",&id,&w);
        wis[id]=w;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",xu+i,xv+i);
        g[xu[i]].push_back(xv[i]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]&&wis[i]!=1e9) tj(i);
    for(int i=1;i<=n;i++) if(!dfn[i]&&wis[i]==1e9){
        printf("NO\n%d\n",i);
        return 0;
    }
    for(int i=1;i<=m;i++) if(scc[xu[i]]!=scc[xv[i]]) in[scc[xv[i]]]=1;
    for(int i=1;i<=sum;i++) if(!in[i]) ans+=mn[i];
    printf("YES\n%d\n",ans);
    return 0;
}

P2272 [ZJOI2007] 最大半连通子图

首先知道强连通分量是肯定属于半联通分量的，之后不难发现在有向无环图中半联通分量就等价于一条链，我们把缩点后的 $siz$ 看成点权，原问题就变成了找有向无环图中的最长链，拓扑+DP 即可。这里有个小知识，就是缩点后的 scc 编号正好是拓扑序倒过来，所以我们不需要再单独做一遍拓扑排序了。

代码：

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

#define int long long
const int N=1e5+5;
const int M=1e6+5;
int n,m,mod,idx,sum,ans,c;
int xu[M],xv[M],dis[N],dfn[N],low[N],tag[N],scc[N],siz[N],num[N];
stack<int> st;
vector<int> g[N],t[N];
map<pair<int,int>,bool> mp;
queue<int> q;

void tj(int u){
    low[u]=dfn[u]=++idx,tag[u]=1;
    st.push(u);
    for(int v:g[u]){
        if(!dfn[v]){ 
            tj(v);
            low[u]=min(low[u],low[v]);
        }
        else if(tag[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        sum++;
        while(st.size()){
            int x=st.top();
            st.pop();
            scc[x]=sum,tag[x]=0,siz[sum]++;
            if(x==u) break;
        }
    }
}

signed main(){
    cin>>n>>m>>mod;
    for(int i=1;i<=m;i++){
        cin>>xu[i]>>xv[i];
        g[xu[i]].push_back(xv[i]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    for(int i=1;i<=m;i++){
        if(scc[xu[i]]==scc[xv[i]]||mp[{scc[xu[i]],scc[xv[i]]}]) continue;
        mp[{scc[xu[i]],scc[xv[i]]}]=1;
        t[scc[xu[i]]].push_back(scc[xv[i]]);
    }
    for(int i=1;i<=sum;i++) dis[i]=siz[i],num[i]=1,ans=max(ans,dis[i]);
    for(int u=sum;u>=1;u--) for(int v:t[u]){
        if(dis[u]+siz[v]>dis[v]){
            dis[v]=dis[u]+siz[v];
            num[v]=num[u];
        }
        else if(dis[u]+siz[v]==dis[v]) (num[v]+=num[u])%=mod;
        ans=max(ans,dis[v]);
    }
    for(int u=1;u<=sum;u++) if(dis[u]==ans) (c+=num[u])%=mod;
    cout<<ans<<endl<<c;
    return 0;
}

P3275 [SCOI2011] 糖果

按关系建边，之后缩点。如果缩点后存在强连通分量内的边边权为 $1$，说明无解，输出 -1；否则按照拓扑序 DP 即可。

代码：

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

#define int long long
const int N=1e5+5;
int n,k,idx,sum,ans;
int xu[N],xv[N],xw[N],dis[N],in[N];
int dfn[N],low[N],tag[N],scc[N],siz[N];
stack<int> st;
vector<pair<int,int>> g[N],t[N],e0,e1;
map<pair<int,int>,bool> m0,m1;
queue<int> q;

void tj(int u){
    low[u]=dfn[u]=++idx,tag[u]=1;
    st.push(u);
    for(auto [v,w]:g[u]){
        if(!dfn[v]){ 
            tj(v);
            low[u]=min(low[u],low[v]);
        }
        else if(tag[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        sum++;
        while(st.size()){
            int x=st.top();
            st.pop();
            scc[x]=sum,tag[x]=0,siz[sum]++;
            if(x==u) break;
        }
    }
}

signed main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        int op,u,v;
        cin>>op>>u>>v;
        if(op==1){
            g[u].push_back({v,0}),e0.push_back({u,v});
            g[v].push_back({u,0}),e0.push_back({v,u});
        }
        if(op==2) g[u].push_back({v,1}),e1.push_back({u,v});
        if(op==3) g[v].push_back({u,0}),e0.push_back({v,u});
        if(op==4) g[v].push_back({u,1}),e1.push_back({v,u});
        if(op==5) g[u].push_back({v,0}),e0.push_back({u,v});
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i);
    for(auto[u,v]:e1){
        if(scc[u]==scc[v]){
            cout<<-1;
            return 0;
        }
    }
    for(auto[u,v]:e0){
        if(scc[u]==scc[v]||m0[{scc[u],scc[v]}]) continue;
        m0[{scc[u],scc[v]}]=1,in[scc[v]]=1;
        t[scc[u]].push_back({scc[v],0});
    }
    for(auto[u,v]:e1){
        if(scc[u]==scc[v]||m1[{scc[u],scc[v]}]) continue;
        m1[{scc[u],scc[v]}]=1,in[scc[v]]=1;
        t[scc[u]].push_back({scc[v],1});
    }
    fill(dis+1,dis+1+sum,1);
    for(int u=sum;u>=1;u--) for(auto[v,w]:t[u]) dis[v]=max(dis[v],dis[u]+w);
    for(int i=1;i<=sum;i++) ans+=dis[i]*siz[i];
    cout<<ans;
    return 0;
}

P1661 扩散

我们知道两个点联通的时刻应该是他们的曼哈顿距离除以二向上取整，我们对所有点对建边，跑最小生成树，答案就是最小生成树中最大的边权。

代码：

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

#define int long long
const int N=300;
int n,ans;
int x[N],y[N],fa[N];
vector<pair<int,pair<int,int>>> e;
vector<pair<int,int>> t[N];

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void kk(){
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++) fa[i]=i;
    int num=0;
    for(auto[w,pii]:e){
        auto[u,v]=pii;
        int fu=find(u),fv=find(v);
        if(fu==fv) continue;
        ans=max(ans,w);
        fa[fv]=fu,num++;
    }
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) e.push_back({ceil((abs(x[i]-x[j])+abs(y[i]-y[j]))*1.0/2),{i,j}});
    kk();
    cout<<ans;
    return 0;
}

模拟赛 T1

按题意模拟，我们先求出 $d$ 数组，再按顺序填数，答案数组就算出来了。

代码：

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

const int N=1e5+5;
int n;
int a[N],d[N],ans[N];

signed main(){
    cin>>n;
    int hd=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i==1||a[i]-a[i-1]!=1) d[a[i]]=++hd;
        else d[a[i]]=hd;
    }
    for(int i=1;i<=n;i++){
        ans[i]=d[i];
        while(d[i+1]==d[i]) ans[++i]=++hd;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" "; 
    return 0;
}

模拟赛 T2

考虑一个点合并了 $x$ 次，其中作为主场合并了 $k1$ 次，作为客场合并了 $k2$ 次。

$$
\begin{aligned}
存活方案数&=总方案数\times 存活概率 \\
&=3^n\cdot (\frac{2}{3})^{k1}\cdot (\frac{1}{3})^{k2}
\end{aligned}
$$

考虑并查集，不使用路径压缩，而是使用按秩合并，在合并路径上记录主客场合并次数的增量，并注意要把父节点的抵消掉。

代码：

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

#define int long long
const int N=2e5+5;
const int mod=998244353;
int n,m;
int ans[N],fa[N],home[N],away[N],siz[N];

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

int find(int x){
    if(x==fa[x]) return x;
    return find(fa[x]);
}

void merge(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx==ry) return;
    if(siz[ry]>siz[rx]){
        fa[rx]=ry;
        away[ry]++;
        home[rx]+=1-home[ry],away[rx]-=away[ry];
        siz[ry]+=siz[rx];
    }
    else{
        fa[ry]=rx;
        home[rx]++;
        home[ry]-=home[rx],away[ry]+=1-away[rx];
        siz[rx]+=siz[ry];
    }
}

int get(int x){
    int k1=home[x],k2=away[x];
    while(x!=fa[x]){
        x=fa[x];
        k1+=home[x],k2+=away[x];
    }
    return (qpow(3,n-k1-k2)*qpow(2,k1))%mod;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    while(m--){
        int op,u,v;
        cin>>op;
        if(op==1){
            cin>>u>>v;
            merge(u,v);
        }
        else{
            cin>>u;
            cout<<get(u)<<"\n";
        }
    }
    return 0;
}