BZOJ 2561 最小生成树(最小割模型)

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解:

我们先来考虑一下我们在使用kruskal算法的时候是怎么生成最小生成树的。

Kruskal算法是一种贪心算法,每次选择边权最小的一条边,检测一下两个端点是否都在一个并查集里,如果不是就加上这一条边,代表最小生成树选择这一条边。

于是这便是此题的关键,如果想要让新加进去的边可能出现在最小生成树中,那么在所有边权小于新边的边集中,就不能有一个子集使得新边的u和v连通。

如果有这样的边集,我们就要通过删边去破坏掉,而且使得破坏掉的边尽可能的少。

诶这不是完美契合最小割模型吗……可是这数据范围……

放心,dinic能顶得住……网络流的复杂度从来都是玄学,这话可不是假的……

于是对于最小生成树,我们就将所有的小于新边权值的边选出来建一张图,每条正向边的容量均为1,求出u,v之间的最小割,就是求出u,v之间的最大流,就可以得出最小生成树部分的答案。

对于最大生成树,其实和最小生成树类似,类比一下就可以了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 2e5+5;
struct edge{
    int fr,to,next,cap;
}e[maxm<<3];
int cnt = 0;
int h[maxn];
int cur[maxn],d[maxn];
const int INF = 1e9;
struct edge2{
    int fr,to,dis;
}e2[maxm];
int n,m;
/*
bool cmp(edge2 a,edge2 b){
    return a.dis < b.dis;
}//其实不用排序
*/
void add(int u,int v,int c){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
    e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr = v;e[cnt].to = u;e[cnt].cap = 0;
    e[cnt].next = h[v];h[v] = cnt++;
    return;
}
bool BFS(int s,int t){
    queue<int>q;
    for(int i = 1;i <= n;++i){
        d[i] = -1;
    }
    q.push(s);
    d[s] = 0;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = h[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(d[v] == -1 && e[i].cap > 0){
                d[v] = d[now]+1;
                q.push(v);
            }
        }
    }
    if(d[t] != -1)return true;
    return false;
}
int DFS(int x,int a,int t){
    if(x == t || a == 0)return a;
    int flow = 0,f;
    for(int &i = cur[x];i != -1;i = e[i].next){
        int v = e[i].to;
        if(d[v] == d[x] + 1 && e[i].cap > 0){
            f = min(a - flow,e[i].cap);
            f = DFS(v,f,t);
            flow += f;
            e[i].cap -= f;
            e[i^1].cap += f;
        }
    }
    return flow;
}
int dinic(int s,int t){
    int flow = 0;
    while(BFS(s,t)){
        for(int i = 1;i <= n;++i)cur[i] = h[i];
        flow += DFS(s,INF,t);
    }
    return flow;
}
int u,v,l;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;++i){
        cin >> e2[i].fr >> e2[i].to >> e2[i].dis;
    }
    int j = 0;
    memset(h,-1,sizeof(h));
    cnt = 0;
    int ans = 0;
    cin >> u >> v >> l;
    for(int i = 1;i <= m;++i){
        if(e2[i].dis < l){
            add(e2[i].fr,e2[i].to,1);
            add(e2[i].to,e2[i].fr,1);
        }
    }
    ans += dinic(u,v);
    memset(h,-1,sizeof(h));
    cnt = 0;
    for(int i = 1;i <= m;++i){
        if(e2[i].dis > l){
            add(e2[i].fr,e2[i].to,1);
            add(e2[i].to,e2[i].fr,1);
        }
    }
    ans += dinic(u,v);
    cout << ans << endl;
    return 0;
}

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00