「BZOJ2654」tree

最小生成樹+二分答案。

最開始并沒有覺得可以二分答案，因為答案并不單調啊。

其實根據題意，白邊的數目肯定大于need條，而最小生成樹的白邊數并不等于need（廢話），可以二分將每條白邊的權值+mid，這樣就可以控制最小生成樹中白邊的條數，

對于一個mid，將所有的白邊權值加mid，然后跑kruskal，求出最小生成樹中白邊的個數num以及此時的權值和ans（要減去mid*need），如果num=need直接輸出ans，如果num<need

則讓r=mid繼續二分，如果num>need,則要記錄一下此時的答案（注意此時的答案并不是ans-mid*num，而是ans-mid*need），因為有可能會出現如下情況：要求8條白邊，mid=0時num=12，mid=1時num=0，無法是num恰好等于need，此時記錄的數據就是答案。

#include<algorithm> #include<iostream> #include<cstdio> #define INF 0x7fffffff using namespace std; struct edge {int u,v,w,c,nxt;#define u(x) ed[x].u#define v(x) ed[x].v#define w(x) ed[x].w#define c(x) ed[x].c#define n(x) ed[x].nxtfriend bool operator < (edge a,edge b){return a.w==b.w?(a.c<b.c):(a.w<b.w);} }ed[100010]; int first[50010],num_e; #define f(x) first[x] int f[50010]; int v,e,n,nb; int l=-500,r=500,mid,ans,eans=INF;int getf(int x){return (f[x]==x)?x:f[x]=getf(f[x]);} void hb(int x,int y){x=getf(x),y=getf(y),f[y]=x;} inline void add(int u,int v,int w,int c); int kruskal() {int num=0;ans=0;for(int i=0;i<=v;i++)f[i]=i;sort(ed+1,ed+num_e+1);for(int i=1;i<=num_e;i++)if(getf(u(i))!=getf(v(i))){ans+=w(i);hb(u(i),v(i));if(!c(i))num++;}return num; } signed main() { // freopen("9.in","r",stdin); // freopen("in.txt","r",stdin);scanf("%d%d%d",&v,&e,&n);for(int i=0;i<=v;i++)f[i]=i;int s,t,w,c;for(int i=1;i<=e;i++){scanf("%d%d%d%d",&s,&t,&w,&c);add(s,t,w,c);if(!c)nb++;}sort(ed+1,ed+num_e+1);int num;while(l<r-1){mid=(l+r)>>1;for(int i=1;i<=num_e;i++)if(!c(i))w(i)+=mid;num=kruskal();if(num==n){printf("%d\n",ans-mid*num);return 0;}else if(num<n)r=mid;else {l=mid;eans=ans-mid*n;}for(int i=1;i<=num_e;i++)if(!c(i))w(i)-=mid;}printf("%d\n",eans); } inline void add(int u,int v,int w,int c) {++num_e;u(num_e)=u;v(num_e)=v;w(num_e)=w;c(num_e)=c;n(num_e)=f(u);f(u)=num_e; }

?

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11178564.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。