首页 > 代码库 > bzoj2654 tree

bzoj2654 tree

2024-10-04 03:10:39   215人阅读

Description

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。 

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

 

正解：二分+$kruskal$。

简直是一道神题啊。。

如果直接$kruskal$求最小生成树，是无法保证白边数量的，那么我们考虑如果改变白边的数量。我们可以把白边全部都加上一个权值，也就是我们二分的值，然后跑最小生成树，同时记录白边数量。当白边数量$>=need$时，$l=mid+1$，否则$r=mid-1$，更新答案就是这棵生成树的权值和减去所有白边的增量。

 

 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 (200010)15 #define il inline16 #define RG register17 #define ll long long18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)19 20 using namespace std;21 22 struct edge{ int u,v,w,c; }g[N];23 24 int fa[N],n,m,ans,need;25 26 il int gi(){27     RG int x=0,q=1; RG char ch=getchar();28     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();29     if (ch==‘-‘) q=-1,ch=getchar();30     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();31     return q*x;32 }33 34 il int cmp(const edge &a,const edge &b){35     if (a.w==b.w) return a.c<b.c; return a.w<b.w;36 }37 38 il int find(RG int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }39 40 il int check(RG int key){41     for (RG int i=1;i<=m;++i) if (!g[i].c) g[i].w+=key;42     sort(g+1,g+m+1,cmp); RG int tt=0,sum=0;43     for (RG int i=1;i<=n;++i) fa[i]=i;44     for (RG int i=1,x,y,k=0;i<=m;++i){45     x=find(g[i].u),y=find(g[i].v);46     if (x!=y) ++k,fa[x]=y,tt+=g[i].c^1,sum+=g[i].w;47     if (k==n-1) break;48     }49     if (tt>=need) ans=sum-tt*key;50     for (RG int i=1;i<=m;++i) if (!g[i].c) g[i].w-=key;51     return tt>=need;52 }53 54 il void find(){55     RG int l=-100,r=100,mid;56     while (l<=r){57     mid=(l+r)>>1;58     if (check(mid)) l=mid+1; else r=mid-1;59     }60     return;61 }62 63 il void work(){64     n=gi(),m=gi(),need=gi();65     for (RG int i=1;i<=m;++i)66     g[i].u=gi()+1,g[i].v=gi()+1,g[i].w=gi(),g[i].c=gi();67     find(); printf("%d\n",ans); return;68 }69 70 int main(){71     File("tree");72     work();73     return 0;74 }

 

bzoj2654 tree


联系
我们