hdu 4253（经典题目：二分+最小生成树）
时间：2014-03-05 17:37:10
收藏：0
阅读：488
题意：就是说有A、B两个公司要修路，有m条路，可能是属于A修的，也可能是属于B修的，现在要求所有路都联通的情况下的最小权值，并且A公司必须要修k条路。
同：
代码：
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117 |
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using
namespace std;struct
node{ int
v1,v2; int
w;} s[100005],t[100005];int
n,m,k,cnts,cntt;int
father[100005],sum;int
cmp(const
node a,const
node b){ if(a.w<b.w) return
1; else return
0;}int
find(int
x){ int
i=x,root; while(x!=father[x]) x=father[x]; root=x; x=i; while(x!=father[x]) { i=father[x]; father[x]=root; x=i; } return
root;}int
deal(int
x){ for(int
i=0; i<=n; i++) father[i]=i; int
lens=0,lent=0,pp=0; sum=0; while(lens<cnts||lent<cntt) { if(s[lens].w+x<=t[lent].w) { int
s1=find(s[lens].v1); int
s2=find(s[lens].v2); if(s1!=s2) { father[s1]=s2; sum+=s[lens].w+x; pp++; } lens++; } else { int
s1=find(t[lent].v1); int
s2=find(t[lent].v2); if(s1!=s2) { father[s1]=s2; sum+=t[lent].w; } lent++; } } if(pp>=k) return
1; else
return 0;}int
main(){ int
text=0; while(scanf("%d%d%d",&n,&m,&k)>0) { cnts=0,cntt=0; for(int
i=0; i<m; i++) { int
v1,v2,w,tmp; scanf("%d%d%d%d",&v1,&v2,&w,&tmp); if(tmp==0) { s[cnts].v1=v1; s[cnts].v2=v2; s[cnts].w=w; cnts++; } if(tmp==1) { t[cntt].v1=v1; t[cntt].v2=v2; t[cntt].w=w; cntt++; } } sort(s,s+cnts,cmp); sort(t,t+cntt,cmp); t[cntt].w=s[cnts].w=(1<<29); printf("Case %d: ",++text); int
l=-1000,r=1000; int
ans=0; while(l<=r) { //sum=0; int
mid=(l+r)/2; if(deal(mid)) { l=mid+1; ans=sum-mid*k; } else
r=mid-1; } printf("%d\n",ans); } return
0;} |
hdu 4253（经典题目：二分+最小生成树）,布布扣,bubuko.com
原文：http://www.cnblogs.com/ziyi--caolu/p/3581337.html
评论（0）