2654: tree
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2733 Solved: 1124
[Submit][Status][Discuss]Description
给你一个无向带权连通图&＃xff0c;每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。
Input
第一行V,E,need分别表示点数&＃xff0c;边数和需要的白色边数。接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)&＃xff0c;边权&＃xff0c;颜色(0白色1黑色)。
Output
一行表示所求生成树的边权和。V<&＃61;50000,E<&＃61;100000,所有数据边权为[1,100]中的正整数。
Sample Input
2 2 1
0 1 1 1
0 1 2 0Sample Output
2HINT
原数据出错&＃xff0c;现已更新 by liutian,但未重测---2016.6.24
Source
[Submit][Status][Discuss]
一种叫WQS二分的思想&＃xff0c;据说[九省联考2018]林克卡特树用到了这个东西。
tsinsen.com/resources/Train2012-sol-wqs.pdf
但是这道题不看论文也可以直接做&＃xff0c;将每条白边加上x后求MST&＃xff0c;设树上的白边的个数为f(x)&＃xff0c;可以确定f(x)是单调不增的&＃xff0c;二分即可。
但可能f(mid)>k,f(mid&＃43;1)
https://www.cnblogs.com/NaVi-Awson/p/7252243.html
1 #include
2 #include
3 #define rep(i,l,r) for (int i&＃61;l; i<&＃61;r; i&＃43;&＃43;)
4 typedef long long ll;
5 using namespace std;
6
7 const int N&＃61;100100;
8 int n,m,cnt,tot,k,ans,u[N],v[N],w[N],c[N],fa[N];
9 struct E{ int u,v,w,c; }e[N];
10
11 bool operator<(E a,E b){ return a.w&＃61;&＃61;b.w ? a.c
12 int find(int x){ return x&＃61;&＃61;fa[x] ? x : fa[x]&＃61;find(fa[x]); }
13
14 bool check(int x){
15 tot&＃61;cnt&＃61;0;
16 rep(i,1,n) fa[i]&＃61;i;
17 rep(i,1,m){
18 e[i].u&＃61;u[i]; e[i].v&＃61;v[i]; e[i].w&＃61;w[i]; e[i].c&＃61;c[i];
19 if(!c[i])e[i].w&＃43;&＃61;x;
20 }
21 sort(e&＃43;1,e&＃43;m&＃43;1);
22 rep(i,1,m){
23 int p&＃61;find(e[i].u),q&＃61;find(e[i].v);
24 if(p!&＃61;q){
25 fa[p]&＃61;q; tot&＃43;&＃61;e[i].w;
26 if (!e[i].c) cnt&＃43;&＃43;;
27 }
28 }
29 return cnt>&＃61;k;
30 }
31
32 int main(){
33 scanf("%d%d%d",&n,&m,&k);
34 rep(i,1,m) scanf("%d%d%d%d",&u[i],&v[i],&w[i],&c[i]),u[i]&＃43;&＃43;,v[i]&＃43;&＃43;;
35 int L&＃61;-105,R&＃61;105;
36 while(L<&＃61;R){
37 int mid&＃61;(L&＃43;R)>>1;
38 if(check(mid)) L&＃61;mid&＃43;1,ans&＃61;tot-k*mid; else R&＃61;mid-1;
39 }
40 printf("%d\n",ans);
41 return 0;
42 }
京公网安备 11010802041100号