2561: 最小生成树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1211 Solved: 585
[Submit][Status][Discuss]
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
Sample Output
HINT
对于20%的数据满足N ≤ 10,M ≤ 20,L ≤ 20;
对于50%的数据满足N ≤ 300,M ≤ 3000,L ≤ 200;
对于100%的数据满足N ≤ 20000,M ≤ 200000,L ≤ 20000。
Source
#include<cstdio> #include<cstring> #include<algorithm> #define INF 1000000000 using namespace std; struct node{int x,y,z;}ed[500010]; int n,m,edgenum,ans,source,sink,vs,x,y,z; int vet[500010],next[500010],head[500010],maxv[500010],dis[500010],gap[500010]; bool cmp(node x,node y){return x.z<y.z;} void add(int u,int v,int w) { vet[++edgenum]=v; next[edgenum]=head[u]; head[u]=edgenum; maxv[edgenum]=w; } int dfs(int u,int aug) { if (u==sink) return aug; int mind=vs-1,flow=0; for (int e=head[u];e;e=next[e]) { if (maxv[e]<=0) continue; int v=vet[e]; if (dis[u]==dis[v]+1) { int t=dfs(v,min(aug-flow,maxv[e])); maxv[e]-=t; if (e%2) maxv[e+1]+=t;else maxv[e-1]+=t; flow+=t; if (dis[source]>=vs) return flow; if (aug==flow) break; } mind=min(mind,dis[v]); } if (!flow) { gap[dis[u]]--; if (!gap[dis[u]]) dis[source]=vs; dis[u]=mind+1; gap[dis[u]]++; } return flow; } int maxflow(int s,int t,int n) { int ans=0; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); source=s;sink=t;gap[0]=vs=n; while (dis[source]<vs) ans+=dfs(source,INF); return ans; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].z); sort(ed+1,ed+m+1,cmp); scanf("%d%d%d",&x,&y,&z); for (int i=1;i<=m;i++) if (ed[i].z>=z) break;else {add(ed[i].x,ed[i].y,1);add(ed[i].y,ed[i].x,1);} ans=maxflow(x,y,n); edgenum=0;memset(head,0,sizeof(head)); for (int i=m;i>=1;i--) if (ed[i].z<=z) break;else {add(ed[i].x,ed[i].y,1);add(ed[i].y,ed[i].x,1);} ans+=maxflow(x,y,n); printf("%d\n",ans); }