【题解】BZOJ 2561 最小生成树

Problem

给定一个带权无向图,问最少删除多少条边,使得 $(u,v,w)$ 有可能既出现在最大生成树上,也可能出现在最小生成树上

Thought

$(u,v,w)$ 可能出现在最小生成树上的充要条件是,加入其它边后,没有任何一条比 $w$ 小的边能够使得 $u,v$ 两个块联通

发现这就相当于是求最小割,问删掉多少条小于 $w$ 的边能使得 $(s,t)$ 不连通

最大生成树同理

由于第一步最小割删去的是权值小于 $w$ 的边,第二步删除的是权值大于 $w$ 的边,两者互不影响,恰好满足条件

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 20010;
const int M = 200010;
int n , m , s , t;
struct edge {
    int t , n , flow;
    void add(int _t , int _n , int _flow) {t = _t; n = _n; flow = _flow;}
}e[M << 2];
int head[N] , cur[N] , tot = 1;
int f[N] , d[N];

void addedge(int u , int v , int flow) {
    e[++ tot].add(v , head[u] , flow);
    head[u] = tot;
    e[++ tot].add(u , head[v] , 0);
    head[v] = tot;
}
int dfs(int now , int flow) {
    if(now == t) return flow;
    int use = 0;
    for(int i = cur[now] ; i ; i = e[i].n) {
        cur[now] = i;
        if(e[i].flow > 0 && d[e[i].t] + 1 == d[now]) {
            int tmp = dfs(e[i].t , min(e[i].flow , flow - use));
            use += tmp;
            e[i].flow -= tmp;
            e[i ^ 1].flow += tmp;
            if(use == flow) return use;
        }
    }
    cur[now] = head[now];
    if(! -- f[d[now]])
        d[s] = n;
    ++ f[++ d[now]];
    return use;
}
int U[M] , V[M] , W[M];
int main() {
    n = read(); m = read();
    for(int i = 1 ; i <= m ; ++ i) {
        U[i] = read();
        V[i] = read();
        W[i] = read();
    }
    s = read(); t = read();
    int l = read();
    for(int i = 1 ; i <= m ; ++ i)
        if(W[i] < l) {
            addedge(U[i] , V[i] , 1);
            addedge(V[i] , U[i] , 1);
        }
    f[0] = n; int ans = 0;
    while(d[s] < n)
        ans += dfs(s , 1 << 30);
    memset(head , 0 , sizeof(head));
    tot = 1;
    memset(e , 0 , sizeof(e));
    memset(d , 0 , sizeof(d));
    memset(f , 0 , sizeof(f));
    for(int i = 1 ; i <= m ; ++ i)
        if(W[i] > l) {
            addedge(U[i] , V[i] , 1);
            addedge(V[i] , U[i] , 1);
        }
    f[0] = n;
    while(d[s] < n)
        ans += dfs(s , 1 << 30);
    printf("%d\n" , ans);
    return 0;
}
Comments

添加新评论