2654: tree
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 2398 Solved: 1003
[Submit][Status][Discuss]
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
0 1 1 1
0 1 2 0
Sample Output
2
HINT
原数据出错，现已更新 by liutian,但未重测---2016.6.24
Source
一开始竟然忘记给边排序了……还有在排序的过程中权值相同的白色的边排在前面！！！就是因为这个地方WA了一次QAQ
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX1=5e5+5; 5 const int MAX2=1e6+5; 6 int n,m,need,tmp,ans; 7 int fa[MAX1]; 8 struct Node{ 9 int u,v; 10 int col,wei; 11 bool operator < (const Node &tt) const { 12 if (wei!=tt.wei) return wei<tt.wei; 13 else return col<tt.col;//非常重要！！！ 14 } 15 }a[MAX2],b[MAX2]; 16 inline int read(){ 17 int an=0,x=1;char c=getchar(); 18 while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();} 19 while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();} 20 return an*x; 21 } 22 int getfather(int x){ return fa[x]==x?x:fa[x]=getfather(fa[x]);} 23 bool feasible(int x){ 24 int i,j,zt; 25 tmp=zt=0; 26 for (i=1;i<=n;i++) fa[i]=i; 27 for (i=1;i<=m;i++){ 28 b[i]=a[i]; 29 if (!b[i].col) b[i].wei+=x; 30 } 31 sort(b+1,b+m+1); 32 for (i=1;i<=m;i++){ 33 int tx=getfather(b[i].u); 34 int ty=getfather(b[i].v); 35 if (tx!=ty){ 36 fa[tx]=ty; 37 tmp+=b[i].wei; 38 if (!b[i].col)zt++; 39 } 40 } 41 return zt>=need; 42 } 43 int main(){ 44 freopen ("tree.in","r",stdin);freopen ("tree.out","w",stdout); 45 int i,j,u,v,col,wei; 46 n=read();m=read();need=read(); 47 for (i=1;i<=m;i++) a[i].u=read(),a[i].v=read(),a[i].wei=read(),a[i].col=read(),a[i].u++,a[i].v++; 48 int low=-100,high=100,mid; 49 while (low<=high){ 50 mid=(low+high)>>1; 51 if (feasible(mid)) ans=tmp-need*mid,low=mid+1; 52 else high=mid-1; 53 } 54 printf("%d",ans); 55 return 0; 56 }