BZOJ 2561: 最小生成树

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

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

题解
考虑最小割(哈哈，没想到吧 ， 我也没想到) ， 先考虑最小生成树 ， 最大生成树同理。
如果一个边(u , v , c) 会被用到当且仅当使用那些个权值比c小的边无法使u,v联通 ， 于是乎 ，我们把所有权值小于c的边连起来，容量是1，跑一边u，v的最小割即可 ，最大生成树的同理 ， 再跑一遍，加起来即可，建议做一下捆绑题目BZOJ2521

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 200010 , inf = 1e7;
inline int read()
{
    register int x = 0 , f = 0; register char c = getchar();
    while(c < '0' || c > '9') f |= c == '-' , c = getchar();
    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
    return f ? -x : x;
}
int n , m , S , T , lim , cnt = 1;
int head[N] , d[N];
struct Edge{ int u , v , val; } s[N];
struct edge{ int v , c , nex; } e[N*4];
inline void add(int u , int v , int c) { e[++cnt].v = v; e[cnt].nex = head[u]; e[cnt].c = c; head[u] = cnt; /* e[++cnt].v = u; e[cnt].nex = head[v]; e[cnt].c = 0; head[v] = cnt; */ return ; }
inline bool cmp(const Edge &A , const Edge &B) { return A.val < B.val; }
 
queue<int> q;
bool bfs()
{
    for(int i = 1 ; i <= n ; ++i) d[i] = 0; d[S] = 1; q.push(S);
    while(q.size())
    {
        int x = q.front(); q.pop(); 
        for(int i = head[x] , v ; i ; i = e[i].nex)
        {
            v = e[i].v; if(d[v] || e[i].c == 0) continue;
            d[v] = d[x] + 1; q.push(v);
        }
    }
    return d[T] != 0;
}
 
int dfs(int x , int flow)
{
    if(x == T || flow == 0) return flow;
    int res = 0 , k;
    for(int i = head[x] , v ; i ; i = e[i].nex)
    {
        v = e[i].v; if(e[i].c == 0 || d[v] != d[x] + 1) continue;
        k = dfs(v , min(e[i].c , flow));
        if(k)
        {
            e[i].c -= k; e[i^1].c += k; res += k; flow -= k;
            if(flow == 0) return res;
        }
        else d[v] = 0;
    }
    return res;
}
 
int Dinic()
{
    int ans = 0 , flow;
    while(bfs()) while(flow = dfs(S , inf)) ans += flow;
    return ans;
}
 
int main()
{
    n = read(); m = read();
    for(int i = 1 ; i <= m ; ++i) s[i].u = read() , s[i].v = read() , s[i].val = read();
    S = read(); T = read(); lim = read();
    sort(s + 1 , s + 1 + m , cmp);
    int posl = lower_bound(s + 1 , s + 1 + m , (Edge){ 0 , 0 , lim} , cmp) - s - 1;
    int posr = upper_bound(s + 1 , s + 1 + m , (Edge){ 0 , 0 , lim} , cmp) - s;
    for(int i = 1 ; i <= posl ; ++i) add(s[i].u , s[i].v , 1) , add(s[i].v , s[i].u , 1);
    int ans = Dinic();
    memset(head , 0 , sizeof head); cnt = 1;
    for(int i = m ; i >= posr ; --i) add(s[i].u , s[i].v , 1) , add(s[i].v , s[i].u , 1);
    cout << ans + Dinic() << '
';
    return 0;
}