【图论】【生成树】(AtCoder Regular Contest 093 E) Bichrome Spanning Tree

86 阅读 0 评论 57 点赞

我是靠谱客的博主自由篮球，最近开发中收集的这篇文章主要介绍【图论】【生成树】(AtCoder Regular Contest 093 E) Bichrome Spanning Tree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

给出一个N个点M条边无向连通图，现在需要给每条边染色（黑/白），染色完毕后，算出一颗至少包含一条黑边与一条白边的最小生成树，要求这个生成树的权值和为X，求染色的方案数。

$Nleq 1000,Mleq 2000$

分析：

Atcoder的题的确很锻炼思维。

首先，一个众所周知的最小生成树算法：破圈算法。这就是本题解法的基础。
简述一下破圈算法：
依次加入每一条边，若边连接的两点(u,v)不在一个联通块内，则连上这条边。
否则，如果连上这条边，就会形成一个环。我们加入这条边，再从环中删去一条权值最大的边，剩下的图一定没有环，并且各点的联通性不会改变。证明很容易，这里不再赘述。

再引到这道题上面来：
很容易发现，若原图的最小生成树中，同时含有黑、白两种颜色的边，则最后的权值一定是这颗最小生成树的权值。

那么再考虑原图的最小生成树中，所有边同为黑/白的情况。
这时候，我们肯定要加入一条颜色不同的边，并且还要使得最后的生成树权值尽量小。（注意，一定只会加入一条边，不会加入两条及以上，证明可以自己思考，很容易）

一个错误的想法：直接将所有未选入最小生成树的边，按照权值大小排序，如果选中第i条边，则要求前i-1条边的颜色与最小生成树的颜色一样，后面的边任意染色，第i条边与最小生成树反色。

这应该是最直观的想法，不过，如果对破圈算法的思想了解足够透彻，就会发现，这种思路绝对是错的。

根据破圈算法的描述，每次加入一条边时，删去的是整个环上权值最大的边。并且对于任意一种插入顺序，都能得到一个权值相同的最小生成树（可能有边不同）。重点就在这里：我们插入这条边后，同时还删去了一条原来的环上权值最大的边。所以每条边的贡献，应该是：该边的权值-最小生成树两点路径间最大权值。

所以，正确的方式应该是：按每条边的贡献由小到大排序，考虑所有：贡献+原最小生成树权值=X的边，分别计算其加入最小生成树的染色方案。

最后，还需要考虑如果X=最小生成树的权值和。
这种情况，还需要额外计算一种情况：即原最小生成树内同时含有黑、白边。
这种情况可以通过（总方案数-最小生成树所有边颜色相同的方案数）算出来。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1010
#define MAXM 2010
#define MOD 1000000007
using namespace std;
int diff[MAXM];
struct node{
    int u,v,len;
    node () {}
    node (int u1,int v1,int len1):u(u1),v(v1),len(len1) {}
    bool operator < (const node &x) const {
        return len<x.len;
    }
}line[MAXM];
bool used[MAXM];
long long x,sum;
int fa[MAXN],fal[MAXN],deep[MAXN];
vector<int> a[MAXN],w[MAXN];
int get_fa(int x){
    if(fa[x]==0)
        return x;
    fa[x]=get_fa(fa[x]);
    return fa[x];
}
void build(int x,int fa1){
    fa[x]=fa1;
    deep[x]=deep[fa1]+1;
    for(int i=0;i<a[x].size();i++){
        if(a[x][i]==fa1){
            fal[x]=w[x][i];
            continue;
        }
        build(a[x][i],x);
    }
}
int find_max(int u,int v){
    int maxv=0;
    if(deep[u]<deep[v])
        swap(u,v);
    while(deep[u]>deep[v]){
        maxv=max(maxv,fal[u]);
        u=fa[u];
    }
    while(u!=v){
        maxv=max(maxv,max(fal[u],fal[v]));
        u=fa[u];
        v=fa[v];
    }
    return maxv;
}
int n,m,u,v,val;
long long bits[MAXM];
void prepare(){
    bits[0]=1;
    for(int i=1;i<=m;i++)
        bits[i]=(bits[i-1]*2ll)%MOD;
}
int main(){
    SF("%d%d",&n,&m);
    prepare();
    SF("%lld",&x);
    for(int i=0;i<m;i++){
        SF("%d%d%d",&u,&v,&val);
        line[i]=node(u,v,val);
    }
    sort(line,line+m);
    for(int i=0;i<m;i++){
        int u=get_fa(line[i].u);
        int v=get_fa(line[i].v);
        if(u!=v){
            fa[u]=v;
            sum+=line[i].len;
            a[line[i].u].push_back(line[i].v);
            a[line[i].v].push_back(line[i].u);
            w[line[i].u].push_back(line[i].len);
            w[line[i].v].push_back(line[i].len);
            used[i]=1;
        }
    }
    x=x-sum;
    if(x<0){
        PF("0");
        return 0;
    }
    memset(fa,0,sizeof fa);
    build(1,0);
    int cnt=0;
    for(int i=0;i<m;i++)
        if(used[i]==0){
            int maxd=find_max(line[i].u,line[i].v);
            diff[++cnt]=line[i].len-maxd;
        }
    sort(diff+1,diff+1+cnt);
    long long res=0;
    if(x==0)
        res=(bits[m]-2ll*bits[m-n+1]+2ll*MOD)%MOD;
    for(int i=1;i<=cnt;i++)
        if(x==diff[i]){
            res+=2ll*bits[cnt-i];
            res%=MOD;
        }
    PF("%lld",res);
}