P5934 [清华集训2012]最小生成树

xiezheyuan · 2022-09-30 21:11:33 · 题解

简要题意

给你一个 N 个点，M 条边的 无向连通 带权图。给定一条边 (u,v,L)，请问需要在原图中删除多少条边，使得将 (u,v,L) 插入图后，它既可能在最小生成树上，又可能在最大生成树上。

对于 100\% 的数据，满足 N\leq 20000,M\leq 200000,L\leq 20000。

思路

update on 2024.1.7 修订一个小错误，感谢 @yyz1005。

如果一条插入边 (u,v,L) 后该边可能在最小生成树上，那么如果将边权小于 L 的边组成一个新图，则新图不连通。

证明：

如果新图连通，则对新图求最小生成树，则最小生成树一定是原图的最小生成树（显然），然后 (u,v,L) 就一定不在任意一个最小生成树中。与前句矛盾，所以必须不连通。
如果新图不连通，则不存在最小生成树，使得任意一条树边边权小于 L。又因为原图连通，所以插入 (u,v,L) 后，原图依旧连通。如果原图的最小生成树边集为 S，则满足 \exists (x,y,z) \in S,z \geq L，但可以知道环上一定有比 L 大的边。 (u,v,L) 插入 S，则最小生成树变为基环树。将环上最大边权的边删除，则该边一定不是 (u,v,L)（除非环上边权都相等），所以 (u,v,L) 可能在插入后的最小生成树上。

（可能有一些不严谨，敬请指正）

同理可得：如果一条插入边 (u,v,L) 后该边可能在最大生成树上，那么如果将边权大于 L 的边组成一个新图，则新图不连通。

所以如果我们建出了这两个新图，则相当于就是在求删除多少条边后全图（其实就是 u\to v）不连通。最小割解决。

最后答案就是两图最小割答案和，由于两个图的割集的交集一定为空集（因为它们没有相同的点），所以可以加法原理。

最后说一句，为什么是题面可能是最小（最大）生成树呢，因为可能有边权相等的边。

时间复杂度 O(\operatorname{maxflow}(n,m))，可以通过本题。

代码

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

int n,m;
const int N = 200000+5,M = 200000+5;
int s,t,U,V,L,ret;

namespace MaxFlow{
    // 自己打一遍 Dinic 最大流，以防忘记
    struct edge{
        int nxt,to,w;
    } g[M<<2];
    int head[N],ec,dis[N],now[N];
    bool vis[N];
    void add(int u,int v,int w){
        g[++ec].nxt=head[u];
        g[ec].to=v;
        g[ec].w=w;
        head[u]=ec;
    }
    int bfs(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        dis[s]=0;
        now[s]=head[s];
        vis[s]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];i;i=g[i].nxt){
                int v=g[i].to;
                if(g[i].w>0 && !vis[v]){
                    q.push(v);
                    vis[v]=1;
                    now[v]=head[v];
                    dis[v]=dis[u]+1;
                    if(v==t){
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int dfs(int x,int sum){
        if(x==t){
            return sum;
        }
        int k,res=sum;
        for(int i=now[x];i&&sum;i=g[i].nxt){
            now[x]=i;
            int v=g[i].to;
            if(g[i].w>0&&(dis[v]==dis[x]+1)){
                k=dfs(v,min(res,g[i].w));
                g[i].w-=k;
                g[i^1].w+=k;
                res-=k;
            }
        }
        return sum-res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,LLONG_MAX);
        }
        return ans;
    }
    void addedge(int u,int v,int cap){
        add(u,v,cap);
        add(v,u,-cap);
    }

    void clean(void){
        ec=0;
        memset(head,0,sizeof(head));
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(g,0,sizeof(g));
    }
}
using namespace MaxFlow;

struct Edge{int from,to,weight;};
vector<Edge> graph;

signed main(){
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        graph.push_back({u,v,w});
    }
    cin>>U>>V>>L;
    s=U,t=V;
    clean();
    for(Edge i:graph){
        if(i.weight < L){
            addedge(i.from,i.to,1);addedge(i.to,i.from,1);
        }
    }
    ret=dinic();
    clean();
    for(Edge i:graph){
        if(i.weight > L){
            addedge(i.from,i.to,1);addedge(i.to,i.from,1);
        }
    }
    cout<<ret+dinic()<<'\n';
    return 0;
}