题链

分析

先找出最小生成树

• 如果边权和大于X，则无解

• 如果边权和小于X，则最小生成树一定染同一种颜色，然后对于每条边，如果经过它的最小生成树小于X,则染同一种颜色，边权和大于X随便染，边权和=X，一定有一条边异色，所以可以容斥解

• 如果边权等于X，则只需要把所有最小生成树为X的边拿出来，只需要1条异色即可，可以容斥

#include<bits/stdc++.h>
#define ll long long
const int p=1e9+7;
using namespace std;

const int N=2005;
int n,m,f[N];
ll K;
struct A{int u,v,k; }E[N];
bool vis[N];
bool cmp(A i,A j) {
	return i.k<j.k;
}
int find(int x) {
	return x==f[x]?x:f[x]=find(f[x]);
} 
int ksm(ll a,int b) {
	ll ret=1;
	while(b) {
		if(b&1) ret=ret*a%p;
		a=a*a%p,b>>=1;
	}
	return ret;
}
int main() {
	scanf("%d%d%lld",&n,&m,&K);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].k);
	}	
	sort(E+1,E+m+1,cmp);
	for(int i=1;i<=n;i++) f[i]=i;
	int sum=0; ll num=0;
	for(int i=1;i<=m;i++) {
		int u=find(E[i].u),v=find(E[i].v);
		if(u!=v) {
			f[u]=v; sum++; vis[i]=1;
			num+=E[i].k;
			if(sum==n-1) break;
		}
	}
	if(num>K||sum!=n-1) {
		puts("0"); return 0;
	}
	if(num<K) {
		num=n-1; int res=0;
		for(int i=1;i<=m;i++) {
			if(!vis[i]) {
				for(int j=1;j<=n;j++) f[j]=j;
				f[E[i].u]=E[i].v; sum=1;
				ll qz=E[i].k;
				for(int j=1;j<=m;j++) {
					int u=find(E[j].u),v=find(E[j].v);
					if(u!=v) {
						f[u]=v; sum++; qz+=E[j].k;
						if(sum==n-1) break;
					}
				}
				if(qz<K) num++;
					else if(qz>K) res++; 
			}
		}
		cout<<(ll)(ksm(2,m-res-num)+p-1)*ksm(2,res+1)%p<<endl;
	} else {
		num=n-1;
		for(int i=1;i<=m;i++) {
			if(!vis[i]) {
				for(int j=1;j<=n;j++) f[j]=j;
				f[E[i].u]=E[i].v; sum=1;
				ll qz=E[i].k;
				for(int j=1;j<=m;j++) {
					int u=find(E[j].u),v=find(E[j].v);
					if(u!=v) {
						f[u]=v,sum++,qz+=E[j].k;
						if(sum==n-1) break;
					}
				}
				if(qz==K) num++;
			}
		}
		cout<<(ll)(ksm(2,num)+p-2)*ksm(2,m-num)%p<<endl;
	}
	return 0;
}

AT3980 [ARC093C] Bichrome Spanning Tree

原文：https://www.cnblogs.com/wsfwsf/p/14862410.html