bzoj2561 最小生成树

Description

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

Input

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

Output

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

Sample Input

3 2
3 2 1
1 2 3
1 2 2

Sample Output

HINT

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

正解：最小割。

讲道理这题并不难，但是我完全没往最小割那方面去想，于是做不出。。

我们知道，要使$(u,v,w)$在最小生成树上，必须割掉边权小于$w$的一些边，使得$u,v$不连通，最大生成树同理。

于是我们对于小于$w$的边连起来，跑一遍最小割，大于$w$的同理。两个最小割加起来，就是答案了。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define N (500010)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
19 
20 using namespace std;
21 
22 struct edge{ int nt,to,flow,cap; }g[N];
23 struct E{ int u,v,w; }e[N];
24 
25 int head[N],d[N],q[N],n,m,u,v,w,num,ans;
26 
27 il int gi(){
28     RG int x=0,q=1; RG char ch=getchar();
29     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
30     if (ch=='-') q=-1,ch=getchar();
31     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
32     return q*x;
33 }
34 
35 il void insert(RG int from,RG int to,RG int cap){
36     g[++num]=(edge){head[from],to,0,cap},head[from]=num; return;
37 }
38 
39 il int cmp(const E &a,const E &b){ return a.w<b.w; }
40 
41 il int bfs(RG int S,RG int T){
42     memset(d,0,sizeof(d));
43     RG int h=0,t=1; q[t]=S,d[S]=1;
44     while (h<t){
45     RG int x=q[++h],v;
46     for (RG int i=head[x];i;i=g[i].nt){
47         v=g[i].to;
48         if (!d[v] && g[i].cap>g[i].flow){
49         d[v]=d[x]+1,q[++t]=v;
50         if (v==T) return 1;
51         }
52     }
53     }
54     return 0;
55 }
56 
57 il int dfs(RG int x,RG int T,RG int a){
58     if (x==T || !a) return a; RG int v,f,flow=0;
59     for (RG int i=head[x];i;i=g[i].nt){
60     v=g[i].to;
61     if (d[v]==d[x]+1 && g[i].cap>g[i].flow){
62         f=dfs(v,T,min(a,g[i].cap-g[i].flow));
63         if (!f){ d[v]=-1; continue; }
64         g[i].flow+=f,g[i^1].flow-=f;
65         flow+=f,a-=f; if (!a) break;
66     }
67     }
68     return flow;
69 }
70 
71 il int maxflow(RG int S,RG int T){
72     RG int flow=0;
73     while (bfs(S,T)) flow+=dfs(S,T,inf);
74     return flow;
75 }
76 
77 il void work(){
78     n=gi(),m=gi();
79     for (RG int i=1;i<=m;++i) e[i].u=gi(),e[i].v=gi(),e[i].w=gi();
80     u=gi(),v=gi(),w=gi(),sort(e+1,e+m+1,cmp),num=1;
81     for (RG int i=1;i<=m;++i){
82     if (e[i].w>=w) break;
83     insert(e[i].u,e[i].v,1),insert(e[i].v,e[i].u,1);
84     }
85     ans+=maxflow(u,v),memset(head,0,sizeof(head)),num=1;
86     for (RG int i=m;i;--i){
87     if (e[i].w<=w) break;
88     insert(e[i].u,e[i].v,1),insert(e[i].v,e[i].u,1);
89     }
90     ans+=maxflow(u,v); printf("%d
",ans); return;
91 }
92 
93 int main(){
94     File("tree");
95     work();
96     return 0;
97 }