ZR 集训 Day25 – 基础图论

ooliver 发布于 5 小时前 45 次阅读 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] 糖果

按关系建边，之后缩点。如果缩点后存在强连通分量内的边边权为