題目連接：點(diǎn)擊查看

題目大意：給出一張 n 個(gè)點(diǎn)和 m 條邊的連通圖，每條邊都有一個(gè)權(quán)值和一個(gè)顏色，顏色用黑色和白色來表示，題目要求恰好使用 k 條白邊的最小生成樹

題目分析：感覺思路很獨(dú)特的一道題目，然鵝就是數(shù)據(jù)出鍋了，感覺挺可惜的，正確的題意應(yīng)該是，要求使用不超過 k 條白邊的最小生成樹

首先如果對原圖直接跑最小生成樹的話，設(shè) cntk 表示選擇的白邊的個(gè)數(shù)，那么 cntk 大概率是不等于 k 的， 那么我們可以考慮對所有的白邊整體放縮，如果將所有的白邊減去一個(gè)值 x ，那么在進(jìn)行克魯斯卡爾排序的時(shí)候，白邊的位置會整體前移，cntk 相應(yīng)的也會變大，反之如果對所有的白邊都加上一個(gè)值 x，那么 cntk 相應(yīng)的也會變大，所以不難看出這個(gè)偏移量 x 和 cntk 之間呈現(xiàn)出單調(diào)的趨勢

這樣我們可以直接對偏移量 x 進(jìn)行二分，每次用克魯斯卡爾求一下最小生成樹，當(dāng) cntk == k 的時(shí)候即為答案所求

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e4+100;int n,m,k,res,cnt,f[N];struct Edge {int u,v,w,t;bool operator<(const Edge& a)const{if(w!=a.w)return w<a.w;return t<a.t;} }edge[N<<1];int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }bool merge(int x,int y) {int xx=find(x),yy=find(y);if(xx!=yy){f[xx]=yy;return true;}return false; }bool check(int x) {for(int i=0;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++)if(edge[i].t==0)edge[i].w+=x;sort(edge+1,edge+1+m);res=0;cnt=0;for(int i=1;i<=m;i++)if(merge(edge[i].u,edge[i].v)){res+=edge[i].w;if(edge[i].t==0)cnt++;}for(int i=1;i<=m;i++)if(edge[i].t==0)edge[i].w-=x;return cnt>=k; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int kase=0;while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(int i=1;i<=m;i++)scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w,&edge[i].t);int l=-100,r=100,ans=0,pos=inf;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=res-k*mid;pos=cnt;l=mid+1;}elser=mid-1;}assert(pos>=k);printf("Case %d: %d\n",++kase,ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4253 Two Famous Companies(二分+最小生成树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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