复习
好久没搞过最小生成树了,先复习一下一些比较重要的东西
kruskal的证明
考虑反证法,如果有一个生成树边集比kruskal跑出来的边集跑出来的最小生成树边集更小,我们就把所有的边按照权值排序,然后从小到大扫过去,扫到一条边就将其像kruskal那样添加进并查集。找到第一条添加进去的不符合kruskal算法的边(即存在另外一条权值小于他,而且添加进去不会成环的边)。我们发现联通的是两个连通块,而如果没有选择的话,将来一定会选择一条权值大于的边来联通这两个联通块,而替换成一定更优秀。
破圈算法
我也不知道是不是叫这个名字。意思就是说,我们可以以任意顺序加入边,如果成了环,就删掉环上最大权值的边,这样得到的一定是最小生成树。这玩意也是可以基于kruskal的证明进行证明的。我们可以归纳证明破圈算法的正确性:
对于已经添加了部分边的图,其最小生成树为。我们再添加一条新的边,如果成了环,令环上的边集为,中最大边为。我们考虑对跑kruskal,当枚举到时必定将其加入最小生成树(因为没有时将加入了最小生成树,一定在之前被枚举到)。当枚举到的时候必定不会选(选了就成环了)。其他中的边可以都保持不变。这样我们就得到了添加后的图的最小生成树。
这道题
分类讨论一波,令这个图最小生成树权值为
必定无解,方案数为0.
我们考虑随便跑个最小生成树,对于中边颜色不同的情况,其他边不管咋选,因为的存在,还是必定满足题目要求,这样的情况数是的。
对于中颜色相同的情况。我们把其他边分成两类。中的边代表使用破圈算法在上加入这条边后,MST大小为X,中的边则加入后大于X。
因为类边必定不会存在于任意一个最小生成树上,所以不影响答案,可以随便涂。而类边只有全部和为同一颜色的情况必定无解,其他情况均有解(随便选一条颜色不同的类边添加上去,根据破圈算法得到的一定还是最小生成树)。所以这种情况数是。把两个式子加起来就是答案。
首先颜色肯定要全部相同,跑出之后剩下的边中,加入之后MST小于的边颜色也要和相同。除此之外的边还是考虑分成类,定义保持不变。现在手上就只需要考虑类边了,做法就和情况完全相同了。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const int maxn=2005;
struct GG{
int u,v,w;
}ori[maxn];
int fa[maxn];
bool cmp(GG a,GG b){return a.w<b.w;}
int get(int x){return (fa[x]==x)?x:(fa[x]=get(fa[x]));}
void uni(int x,int y){fa[get(x)]=get(y);}
int dep[maxn],f[maxn],valtof[maxn];
vi side[maxn],W[maxn];
void dfs1(int u,int fa){
//cout<<">>"<<u<<' '<<fa<<endl;cnt++;
// if(cnt>10)return;
dep[u]=dep[fa]+1;
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
dfs1(v,u);f[v]=u;valtof[v]=W[u][i];
}
}
vi A,B;
int find(int u,int v){
int mx=0;
while(u!=v){
if(dep[u]<dep[v])swap(u,v);
mx=max(mx,valtof[u]);u=f[u];
}
return mx;
}
int ksm(int num,int t){
int res=1;
for(;t;t>>=1,num=1ll*num*num%mod){
if(t&1)res=1ll*num*res%mod;
}
return res;
}
int main(){
rep(i,1,maxn-1)fa[i]=i;
int n,m;scanf("%d%d",&n,&m);
ll X,Y=0;scanf("%lld",&X);
rep(i,1,m){
scanf("%d%d%d",&ori[i].u,&ori[i].v,&ori[i].w);
}
sort(ori+1,ori+1+m,cmp);
rep(i,1,m){
int u=ori[i].u,v=ori[i].v;
if(get(u)!=get(v)){
uni(u,v);Y+=ori[i].w;
side[ori[i].u].pb(ori[i].v);side[ori[i].v].pb(ori[i].u);
W[ori[i].u].pb(ori[i].w);W[ori[i].v].pb(ori[i].w);
}
}
dfs1(1,0);
rep(i,1,maxn-1)fa[i]=i;
rep(i,1,m){
int u=ori[i].u,v=ori[i].v;
if(get(u)!=get(v)){uni(u,v);}
else{
int delta=ori[i].w-find(u,v);
if(Y+delta==X)A.pb(i);
else if(Y+delta>X)B.pb(i);
}
}
ll ans=0;
if(X<Y){ans=0;}
else if(X==Y){
ans=1ll*(ksm(2,n-1)-2)*ksm(2,m-(n-1))%mod;
//cout<<ans<<endl;
ans=(ans+2ll*(ksm(2,A.size())-1)*ksm(2,B.size()))%mod;
}
else
ans=(ans+2ll*(ksm(2,A.size())-1)*ksm(2,B.size()))%mod;
ans=(ans%mod+mod)%mod;
printf("%lld",ans);
return 0;
}