Description

給你一個(gè)無向帶權(quán)連通圖，每條邊是黑色或白色。讓你求一棵最小權(quán)的恰好有need條白色邊的生成樹。 題目保證有解。

Input

第一行V,E,need分別表示點(diǎn)數(shù)，邊數(shù)和需要的白色邊數(shù)。 接下來E行,每行s,t,c,col表示這邊的端點(diǎn)(點(diǎn)從0開始標(biāo)號(hào))，邊權(quán)，顏色(0白色1黑色)。

Output

一行表示所求生成樹的邊權(quán)和。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

Hint

V<=50000,E<=100000,所有數(shù)據(jù)邊權(quán)為[1,100]中的正整數(shù)。

題解

二分+$kruskal$

如果直接$kruskal$求最小生成樹,是無法保證白邊數(shù)量的,那么我們考慮如果改變白邊的數(shù)量。我們可以把白邊全部都加上一個(gè)權(quán)值,也就是我們二分的值,然后跑最小生成樹,同時(shí)記錄白邊數(shù)量。當(dāng)白邊數(shù)量>=$need$時(shí),$l=mid+1$,否則$r=mid?1$,更新答案就是這棵生成樹的權(quán)值和減去所有白邊的增量。

證明:
我們發(fā)現(xiàn),如果我們給白邊增加權(quán)值,做最小生成樹,由于白邊權(quán)值增大,導(dǎo)致不容易選白邊。記$f(x)$為給白邊增加$x$($x$可為負(fù))權(quán)值,做最小生成樹后,選白邊的數(shù)量。可以發(fā)現(xiàn),$f(x)$隨$x$增大而減小,顯然可以二分。
其次,我們發(fā)現(xiàn),由于黑邊的權(quán)值是不變的,與白邊權(quán)值不相互影響。同樣由于白邊之間關(guān)系相對(duì)不變,必然選出的$need$條白邊一定是符合題意的。

1 #include<map> 2 #include<ctime> 3 #include<cmath> 4 #include<queue> 5 #include<stack> 6 #include<cstdio> 7 #include<string> 8 #include<vector> 9 #include<cstring> 10 #include<cstdlib> 11 #include<iostream> 12 #include<algorithm> 13 #define LL long long 14 #define RE register 15 #define IL inline 16 using namespace std; 17 const int V=50000; 18 const int E=100000; 19 20 int mid; 21 int v,e,need,ans,cnt,tmp; 22 struct tt 23 { 24 int u,v,c,col; 25 }edge[E+5]; 26 27 IL int Kruskal(); 28 bool comp(const tt &a,const tt &b) {return a.c+(a.col^1)*mid<b.c+(b.col^1)*mid;} 29 30 int set[V+5]; 31 IL int find(int r) {return set[r]!=-1 ? set[r]=find(set[r]):r;} 32 33 int main() 34 { 35 scanf("%d%d%d",&v,&e,&need); 36 for (RE int i=1;i<=e;i++) scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c,&edge[i].col); 37 int l=-100,r=100; 38 while (l<=r) 39 { 40 mid=(l+r)>>1; 41 if (Kruskal()>=need) l=mid+1,ans=tmp; 42 else r=mid-1; 43 } 44 printf("%d\n",ans); 45 return 0; 46 } 47 48 IL int Kruskal() 49 { 50 tmp=cnt=0; 51 int k=0; 52 memset(set,-1,sizeof(set)); 53 sort(edge+1,edge+1+e,comp); 54 for (RE int i=1;i<=e;i++) 55 { 56 int q=find(edge[i].u); 57 int p=find(edge[i].v); 58 if (p!=q) 59 { 60 k+=edge[i].col^1; 61 set[q]=p; 62 cnt++; 63 tmp+=edge[i].c; 64 if (cnt==v-1) break; 65 } 66 } 67 return k; 68 } BZOJ能過的解法

感謝Hzoi_Maple！

由于$COGS$數(shù)據(jù)會(huì)有不滿足恰好$need$條白邊的情況

打個(gè)比方有這樣的數(shù)據(jù)：加$0$時(shí)大于$need$，加$1$就小于$need$了。

這樣應(yīng)該在跑最小生成樹的時(shí)候把所有的白邊都加上加的那個(gè)權(quán)值，結(jié)果就是最小生成樹的權(quán)值和減去$need*$加上的權(quán)值，多出來的那一部分完全可以當(dāng)做黑邊來看，因?yàn)閿?shù)據(jù)是$100000$的，這樣就可以了。（來自Hzoi_Maple）

排序的時(shí)候，如果邊權(quán)相同，要把白邊放在前面。

要計(jì)算當(dāng)前至多能取多少白邊，當(dāng)然要把白邊放前面。由于保證有解，在$cnt>=need$且$cnt$取最小值的方案下，一定能有黑邊把多余的白邊代替掉。

1 #include<map> 2 #include<ctime> 3 #include<cmath> 4 #include<queue> 5 #include<stack> 6 #include<cstdio> 7 #include<string> 8 #include<vector> 9 #include<cstring> 10 #include<cstdlib> 11 #include<iostream> 12 #include<algorithm> 13 #define LL long long 14 #define RE register 15 #define IL inline 16 using namespace std; 17 const int V=50000; 18 const int E=100000; 19 20 int mid; 21 int v,e,need,ans,cnt,tmp; 22 struct tt 23 { 24 int u,v,c,col,rc; 25 }edge[E+5]; 26 27 IL int Kruskal(); 28 IL void change(); 29 bool comp(const tt &a,const tt &b) {return a.rc==b.rc ? a.col<b.col:a.rc<b.rc;} 30 31 int set[V+5]; 32 IL int find(int r) {return set[r]!=-1 ? set[r]=find(set[r]):r;} 33 34 int main() 35 { 36 scanf("%d%d%d",&v,&e,&need); 37 for (RE int i=1;i<=e;i++) scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c,&edge[i].col); 38 int l=-100,r=100; 39 while (l<=r) 40 { 41 mid=(l+r)>>1; 42 if (Kruskal()>=need) l=mid+1,ans=tmp-need*mid; 43 else r=mid-1; 44 } 45 printf("%d\n",ans); 46 return 0; 47 } 48 49 IL void change() 50 { 51 for (RE int i=1;i<=e;i++) edge[i].rc=edge[i].c+(edge[i].col^1)*mid; 52 } 53 IL int Kruskal() 54 { 55 change(); 56 tmp=cnt=0; 57 int k=0; 58 memset(set,-1,sizeof(set)); 59 sort(edge+1,edge+1+e,comp); 60 for (RE int i=1;i<=e;i++) 61 { 62 int q=find(edge[i].u); 63 int p=find(edge[i].v); 64 if (p!=q) 65 { 66 k+=edge[i].col^1; 67 set[q]=p; 68 cnt++; 69 tmp+=edge[i].rc; 70 if (cnt==v-1) break; 71 } 72 } 73 return k; 74 } COGS能過的解法

轉(zhuǎn)載于:https://www.cnblogs.com/NaVi-Awson/p/7252243.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 2654]tree(陈立杰)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。