「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；
数据保证图中没有自环。
接下来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
3 2 1
1 2 3
1 2 2
Sample Output
1
HINT
对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；
对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。
题解
加入的边为u,v长度L
则所有长度大于L的边不能使得u，v连通
求个最小割即可
小于同理
两次最小割结果相加
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int U,V,L; int n,m,cnt=1,ans; int head[20005],cur[20005],h[20005],q[20005]; struct data{int x,y,v;}a[200005]; struct edge{int to,next,v;}e[1000005]; inline bool operator<(data a,data b) {return a.v<b.v;} void ins(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w; } void insert(int u,int v) {ins(u,v,1);ins(v,u,1);} bool bfs() { for(int i=1;i<=n;i++)h[i]=-1; int t=0,w=1; q[0]=U;h[U]=0; while(t!=w) { int now=q[t];t++; for(int i=head[now];i;i=e[i].next) if(h[e[i].to]==-1&&e[i].v) { h[e[i].to]=h[now]+1; q[w++]=e[i].to; } } if(h[V]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==V)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w;if(e[i].v)cur[x]=i; e[i^1].v+=w;used+=w;if(used==f)return f; } if(used==0)h[x]=-1; return used; } void dinic() { while(bfs()){for(int i=1;i<=n;i++)cur[i]=head[i];ans+=dfs(U,inf);} } int main() { n=read();m=read(); for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].v=read(); U=read();V=read();L=read(); sort(a+1,a+m+1); for(int i=1;i<=m;i++) if(a[i].v<L)insert(a[i].x,a[i].y); else break; dinic(); memset(head,0,sizeof(head));cnt=1; for(int i=m;i;i--) if(a[i].v>L)insert(a[i].x,a[i].y); else break; dinic(); printf("%d",ans); return 0; } |
计数器 9793858
OI 课件=>
OI 课件=>
想问下为啥反向边容量也为1呢？不应该是0吗?