【bzoj2654】 tree

2015.01.27 15:46 Tue | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

  给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。

Input

  第一行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
所有数据边权为[1,100]中的正整数。

题解

想了好久,终于还是不会做……
查了题解,都好简陋啊。。代码倒是a掉了,但是还是不知道这么做为什么是对的
又想了好久,这次终于想出来了
每次给白色边加上一个权值,之后做kruskal,求出用了多少条白色边以及权值和,如果比need少,则减小权值,否则加大,权值可以用二分
而且求出来的最小生成树也一定对应的是原权值图取need条边的最小生成树,可以这么想:
如果在生成树中去掉一条黑边,那么只能在加一条黑边,先加进去的黑边权值一定比后加进去的小,所以产生矛盾
如果在生成树中去掉一条白边,那么也只能再加一条白边,而加完二分出来的权值之后的白边权值的大小关系依然不变,同样满足先加入的一定小于后加入的
于是二分权值加kruskal就好了
另外还需注意一下二分时候的判断问题,见代码

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxm 100005
#define maxn 50005
using namespace std;
int n,m,need,final,ret,ans,cnt;
int f[maxn];
struct edge{
    int u;
    int v;
    int no;
    int _val;
    int val;
}e[maxm]; 
bool cmp(const edge &a,const edge &b)
{
    return a.val==b.val?a.no<b.no:a.val<b.val;//a.val==b.val?a.no>b.no:a.val<b.val;
}
int find(int x)
{
    return f[x]==x?x:(f[x]=find(f[x]));
}
int kruskal()
{
    ret=ans=0;
    cnt=n-1;
    for(int i=0;i<n;i++) f[i]=i;
    for(int p,q,flag,u,v,w,i=1;i<=m&&cnt;i++)
    {
        u=e[i].u,v=e[i].v,w=e[i].val,flag=e[i].no^1;
        p=find(u),q=find(v);
        if(p!=q)
        {
            f[p]=q;
            ans+=w;
            ret+=flag;
            cnt--;
        }
    }
    return ret>=need;//ret<=need;
}
int main()
{
    cin>>n>>m>>need;
    for(int i=1;i<=m;i++)
    scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i]._val,&e[i].no);
    int l=-101,r=101;
    while(l<=r)
    {
        int mid=(l+r)>>1;  
        for(int i=1;i<=m;i++) 
        {
            e[i].val=e[i]._val; 
            if(!e[i].no)
            e[i].val+=mid;
        }   
        sort(e+1,e+m+1,cmp);
        if(kruskal()) l=mid+1,final=ans-mid*need;//r=mid-1,final=ans-mid*need;
        else r=mid-1; //l=mid+1
        //如果按照白边在先为第二关键字排序,则答案一定在>=need中,按照白边在后则一定在<=need中 
    }
    cout<<final;
}```