题目地址：BZOJ：Problem 2561. — 最小生成树

题目描述

给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？

输入输出格式

输入格式：
第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。

输出格式：
输出一行一个整数表示最少需要删掉的边的数量。

输入输出样例

输入样例#1：

3 2
3 2 1
1 2 3
1 2 2

输出样例#1：

1

说明

对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；
对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。

题解

回想一下最小生成树是怎么来找的，以Kruskal算法为例。我们考虑边权 < L的边，这些边如果能够使u和v连通，则我们想加进去的(u, v, L)这条边就没法加入最小生成树了，因此我们需要删掉一些边权 < L的边，使得u和v不能连通。这个可以用最小割来实现。最大生成树同理。由于我们删掉的边中一些是< L的一些是> L的，这两个集合并无交集，因此不需要去重，直接跑两遍最小割把答案加起来就好。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005, MAXM = 400005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXM << 1];
int head[MAXN], tot;

inline void reset() {
    memset(head, -1, sizeof(head)); tot = 0;
}

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];
std::queue<int> que;

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];
bool vis[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) 
        return left;
    int flow = 0; vis[u] = true;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && !vis[v] && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(!left) {
                    level[u] = -1;
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memset(vis, 0, sizeof(vis));
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int n, m, u, v, w;

struct EData {
    int u, v, w;
} edges[MAXM];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    u = readint(); v = readint(); w = readint();
    int ans = 0;
    reset();
    for(int i = 1; i <= m; i++) {
        if(edges[i].w < w) {
            addedge(edges[i].u, edges[i].v, 1);
            addedge(edges[i].v, edges[i].u, 1);
        }
    }
    ans += dinic(u, v);
    reset();
    for(int i = 1; i <= m; i++) {
        if(edges[i].w > w) {
            addedge(edges[i].u, edges[i].v, 1);
            addedge(edges[i].v, edges[i].u, 1);
        }
    }
    ans += dinic(u, v);
    printf("%d", ans);
    return 0;
}