2654: tree

Time Limit:?30 Sec??Memory Limit:?512 MB
Submit:?610??Solved:?225
[Submit][Status][Discuss]

Description

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

?

Input

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

?

Output

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

?

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

HINT

?

數(shù)據(jù)規(guī)模和約定

　　0:V<=10

　　1,2,3:V<=15

　　0,..,19:V<=50000,E<=100000

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

?

Source

?

只想說好巧妙地想法……

對于每條白邊，我們每次給他加一個值x(x∈[-101,101],因為所有邊權(quán)都在這個范圍之內(nèi))，易看出隨著x的增大，白邊在MST中的數(shù)量是漸漸減少的，我們求出每條白邊+x時MST中白邊的最大數(shù)量，因此求出第一個小于need的x，x-1就是我們需要的x，求出此時的MST，即要求的答案。

?

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #include<queue> using namespace std; struct node {int u,v,w,c; } e[100005]; int u[100005],v[100005],w[100005],c[100005],f[50005]; int n,m,need,ans,sum,cnt,l,r; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } bool cmp(node a,node b) {return ((a.w<b.w)||((a.w==b.w)&&(a.c<b.c))); } bool pd(int x) {ans=0;cnt=0;for (int i=1;i<=n;i++) f[i]=i;for (int i=1;i<=m;i++){e[i].u=u[i],e[i].v=v[i],e[i].w=w[i];e[i].c=c[i];if(!c[i])e[i].w+=x;}sort(e+1,e+m+1,cmp);for (int i=1;i<=m;i++){int p=find(e[i].u),q=find(e[i].v);if (p!=q){f[p]=q;ans+=e[i].w;if (e[i].c==0) cnt++;}}return cnt>=need; } int main() {scanf("%d%d%d",&n,&m,&need);for (int i=1;i<=m;i++){scanf("%d%d%d%d",&u[i],&v[i],&w[i],&c[i]);u[i]++; v[i]++;}l=-101; r=101;while (l<=r){int mid=(l+r)/2;if (pd(mid)){l=mid+1;sum=ans-need*mid;}else r=mid-1;}printf("%d",sum); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ws-fqk/p/4660841.html

總結(jié)

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

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