2654: tree

Time Limit: 30 Sec  Memory Limit: 512 MB

Submit: 2893  Solved: 1191

[][][]

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

Sample Output

2

HINT

 

原数据出错，现已更新 by liutian,但未重测---2016.6.24

 

 

    APIO讲的凸优化模板。。。。。

    凸优化大致就是 对限制某种物品选的数量 的dp 的一种手段，（但得适合像最小生成树这样有拟阵性质的贪心）

    

随着二分值的变化，选的物品的数量也会单调变化，并且最优化的都是一种东西。。所以。。。

 

#include
      
       #define ll long longusing namespace std;const int maxn=100005;int n,m,K,L,R,mid,ans,p[maxn];struct lines{	int u,v,w,W,T;	bool operator <(const lines &u)const{		return W==u.W?T
       
        
         =K){ ans=now; return 1;}	else return 0;} inline void solve(){	L=-100,R=100;	while(L<=R){		mid=L+R>>1;		if(work()) L=mid+1;		else R=mid-1;	}}int main(){	scanf("%d%d%d",&n,&m,&K);	for(int i=1;i<=m;i++){		scanf("%d%d%d%d",&l[i].u,&l[i].v,&l[i].w,&l[i].T);		l[i].u++,l[i].v++;	}		solve();		printf("%d\n",ans);	return 0;}