【bzoj 2654】【tree】【二分+最小生成ツリー】

Description
無方向帯権連通図をあげます.各エッジは黒か白です.最小権のちょうどneedの白い辺の生成木を求めさせます.問題は解があることを保証する.
Input
第1行V,E,needはそれぞれ点数,辺数,必要な白色辺数を表す.次に、E行毎にs,t,c,colは、こちらの端点(点0から符号)、辺権、色(0白1黒)を表す.
Output
一行は、求めた木の辺権和を表す.
Sample Input
2 2 1 0 1 1 1 0 1 2 0
Sample Output
2
HINT
データ規模と約束0:V<=10 1,2,3:V<=15 0,..19:V<=50000、E<=100000のすべてのデータのエッジ重みは[1100]の正の整数です.
問題解:明らかに白辺の重み値が大きくなるにつれて発見される.最小生成ツリーの白辺の個数は増加しません.
それからこの性質によって私たちは1つの値を2分することができて、それから毎回白い辺にこの値を加えることができます.最小生成ツリーの白辺の個数を見てみましょう.
最後に答えを減らします.
考え方はとても簡単に見えますが、重要な細部があります.
もしあなたの二分過程で白辺にmidを加えると、あなたが得た白辺の数はneedより大きいです.
白辺にmid+1を加えると、あなたが得た白辺はneedより小さいです.
このような状況は処理できないようだ.
しかし、クルーズカールの加辺順序を考えてみましょう.
このような場合,必ず等しい白辺と黒辺がたくさんあることが分かった.データは合法的だからだ.
白いエッジを黒いエッジに置き換えることができます
だから私たちは白辺数>=needの時に新しい答えをつけなければなりません.
具体的にはans=ans-mid*need;できます.
コード:

#include
#include
#include
using namespace std;
int fa[1000001],n,m,need,l(-105),r(105),mid,temp,ans,r1,r2,cnt,ans2;
struct use{int st,en,c,v;}e[100010];
int find(int x){if (x!=fa[x]) fa[x]=find(fa[x]);return fa[x];}
bool cmp(use a,use b){if (a.v==b.v) return a.c>1;
    for (int i=1;i<=m;i++) {if (e[i].c==0) e[i].v+=mid;}
    for (int i=1;i<=n+1;i++) fa[i]=i;ans=0;temp=0;cnt=0;
    solve();
    if (temp>=need) {l=mid+1;ans2=ans-need*mid;}else r=mid-1;
    for (int i=1;i<=m;i++) if (e[i].c==0) e[i].v-=mid;
  }
  printf("%d
",ans2);
}