tree
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2739 Solved: 1126
[Submit][Status][Discuss]
Description
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
Input
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
Output
一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。
Sample Input
2 2 1
0 1 1 1
0 1 2 0
0 1 1 1
0 1 2 0
Sample Output
2
HINT
原数据出错，现已更新 by liutian,但未重测---2016.6.24
题解：get了一种新的套路，可以二分一个值，让白边都减去这个值，然后排序后，可以发现这样具有二分性
然后可以瞎搞，不过注意权值相等的问题，所以每次需要加的是二分值的的贡献。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue> #define N 50007
#define M 100007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,ned;
int ans,num;
int fa[N];
struct Node
{
int x,y,w,c;
friend bool operator<(Node x,Node y)
{
if (x.w==y.w) return x.c<y.c;
return x.w<y.w;
}
}a[M],e[M]; int find(int num)
{
if (fa[num]!=num) fa[num]=find(fa[num]);
return fa[num];
}
bool judge(int zhi)
{
ans=,num=;
for (int i=;i<=m;i++)
{
e[i]=a[i];
if (!a[i].c) e[i].w+=zhi;
}
sort(e+,e+m+);
for (int i=;i<=n;i++) fa[i]=i;
for (int i=;i<=m;i++)
{
int u=find(e[i].x),v=find(e[i].y);
if (u!=v)
{
fa[v]=u;
if (!e[i].c) num++;
ans+=e[i].w;
}
}
ans-=zhi*num;
if (num>=ned) return true;
else return false;
}
int main()
{
n=read(),m=read(),ned=read();
for (int i=;i<=m;i++)
a[i].x=read()+,a[i].y=read()+,a[i].w=read(),a[i].c=read(); int l=-,r=;
while(l<r)
{
int mid=(l+r+)>>;
if (judge(mid)) l=mid;
else r=mid-;
}
printf("%d\n",ans);
}