首页 > 代码库 > BZOJ2561: 最小生成树
BZOJ2561: 最小生成树
2561: 最小生成树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 558 Solved: 278
[Submit][Status]
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。
Source
2012国家集训队Round 1 day1
题解：
如果连接u-v权值为 l 要成为最小生成树上的边，那么就不能存在比 l 小的边使得u-v连通。做一遍最小割即可。
最大同理。
代码：
View Code
如果连接u-v权值为 l 要成为最小生成树上的边，那么就不能存在比 l 小的边使得u-v连通。做一遍最小割即可。
最大同理。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+5 26 27 #define maxm 5000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,s,t,maxflow,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn]; 61 62 struct edge{int go,next,v;}e[maxm]; 63 struct rec{int x,y,w;}a[maxm]; 64 inline bool cmp(rec a,rec b){return a.w<b.w;} 65 66 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;} 67 68 void insert(int x,int y){ins(x,y,1);ins(y,x,1);} 69 70 bool bfs() 71 72 { 73 74 for(int i=1;i<=n;i++)h[i]=-1; 75 76 int l=0,r=1;q[1]=s;h[s]=0; 77 78 while(l<r) 79 80 { 81 82 int x=q[++l]; 83 84 for(int i=head[x];i;i=e[i].next) 85 86 if(e[i].v&&h[e[i].go]==-1) 87 88 { 89 90 h[e[i].go]=h[x]+1;q[++r]=e[i].go; 91 92 } 93 94 } 95 96 return h[t]!=-1; 97 98 } 99 100 int dfs(int x,int f)101 102 {103 104 if(x==t) return f;105 106 int tmp,used=0;107 108 for(int i=cur[x];i;i=e[i].next)109 110 if(e[i].v&&h[e[i].go]==h[x]+1)111 112 {113 114 tmp=dfs(e[i].go,min(e[i].v,f-used));115 116 e[i].v-=tmp;if(e[i].v)cur[x]=i;117 118 e[i^1].v+=tmp;used+=tmp;119 120 if(used==f)return f; 121 122 }123 124 if(!used) h[x]=-1;125 126 return used;127 128 }129 130 void dinic()131 132 {133 134 while(bfs())135 136 {137 138 for (int i=1;i<=n;i++)cur[i]=head[i];maxflow+=dfs(s,inf);139 140 }141 142 }143 144 int main()145 146 {147 148 freopen("input.txt","r",stdin);149 150 freopen("output.txt","w",stdout);151 152 n=read();m=read();153 for1(i,m)a[i].x=read(),a[i].y=read(),a[i].w=read();154 sort(a+1,a+m+1,cmp);155 s=read();t=read();int w=read();156 for1(i,m)if(a[i].w<w)insert(a[i].x,a[i].y);else break;157 dinic();158 memset(head,0,sizeof(head));tot=1;159 for3(i,m,1)if(a[i].w>w)insert(a[i].x,a[i].y);else break;160 dinic();161 printf("%d\n",maxflow);162 163 return 0;164 165 }
疑问：为何直接建的双向边，回边怎么办？
BZOJ2561: 最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。