AtCoder Regular Contest 093 E： Bichrome Spanning Tree（生成树）

Bichrome Spanning Tree

题意：

给出一个n个点，m条边的无向连通图，现在要给每条边染色，可以染成黑色或者白色。

现在要求在染色完毕后，找出一个至少包含一条黑边和一条白边的最小生成树，使其权值和为X。

问这样的染色方案有多少个？

题解：

题目要求找出一个至少包含一条黑边和白边的最小生成树，那么可能就会存在这种情况:原图的最小生成树所有边都为同色，那这不是我们要求的；我们这时就会去掉一条权值最大的边，再添一条边进来。

那么我们就可以算出包含指定边的最小生成树，方法就是先加我们指定的边，然后从小到大加边。

现在来解决这个问题，我们可以先求出原图的最小生成树，设其权值和为T，那么我们就对接下来的几种情况进行分析:

1.T>X 这种情况方案数为0；

2.T=X 这种情况下，因为边权可能会相等，所以可以继续进行删边加边的操作，直至第一种情况；

3.T<X 这种情况，我们就继续删边加边，找出使T=X相等的边的个数。

最后根据找到边的个数统计一下就好了：

对于第二种情况，设使T=X的边个数为a，其余边为b，那么答案就是(2^a-2)*2^b；

对于第三种情况，一开始使T<X的边只能同色，则方案数为2，则总答案为(2*2^a-2)*2^b，（a,b含义与上相同）。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ,MOD = 1e9+;

int n,m;

ll X;

struct Edge{

    int u,v,w;

    bool operator < (const Edge& A)const{

        return w<A.w;

    }

}e[N];

int f[N];

int find(int x){

    return f[x]==x ? x :f[x]=find(f[x]);

}

ll Kruskal(int edge){

    ll sum = ;

    for(int i=;i<=n+;i++) f[i]=i;

    int fx,fy;

    if(edge){

        fx=find(e[edge].u),fy=find(e[edge].v);

        f[fx]=fy;sum+=e[edge].w;

    }

    for(int i=;i<=m;i++){

        if(i==edge) continue ;

        fx=find(e[i].u);fy=find(e[i].v);

        if(fx!=fy){

            f[fx]=fy;

            sum+=e[i].w;

        }

    }

    return sum;

}

ll qp(ll a,ll b){

    ll ans=;

    while(b){

        if(b&) ans=a*ans%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return ans ;

}

int main(){

    scanf("%d%d%lld",&n,&m,&X);

    for(int i=;i<=m;i++)

        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    sort(e+,e+m+);

    ll t = Kruskal();

    if(t>X){cout<<;return ;}

    int cnt1=,cnt2=;

    for(int i=;i<=m;i++){

        ll now = Kruskal(i);

        if(now==X) cnt1++;

        else if(now>X) cnt2++;

    }

    if(t==X) cout<<(qp(,cnt1)-)*qp(,cnt2)%MOD;

    else cout<<((ll)*qp(,cnt1)-)%MOD*qp(,cnt2)%MOD;

    return ;

}

巴特西

AtCoder Regular Contest 093 E： Bichrome Spanning Tree（生成树）

最新文章

热门文章