1：最小生成树
#include<bits/stdc++.h>
using namespace std;
const int mod=31011;
struct mdzz{
int op,ed,v;
}e[1010];
struct rbq{
int left,right,va;
}a[1010];
int n,m,f[110],ans,q[110],cnt,sum,tot;
int find(int x){return x==f[x]?x:find(f[x]);}
bool cmp(mdzz a,mdzz b){
return a.v<b.v;
}
void dfs(int x,int now,int k)
{
if(now==a[x].right+1)
{
if(k==a[x].va)sum++;
return;
}
int xx=find(e[now].op),yy=find(e[now].ed);
if(xx!=yy)
{
f[xx]=yy;
dfs(x,now+1,k+1);
f[xx]=xx;f[yy]=yy;
}
dfs(x,now+1,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].op,&e[i].ed,&e[i].v);
sort(e+1,e+m+1,cmp);
int tot=0;
for(int i=1;i<=m;i++)
{
if(e[i].v!=e[i-1].v)cnt++,a[cnt].left=i,a[cnt-1].right=i-1;
int xx=find(e[i].op),yy=find(e[i].ed);
if(xx!=yy)f[xx]=yy,a[cnt].va++,tot++;
}
if(tot!=n-1){printf("0");return 0;}
a[cnt].right=m;
ans=1;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=cnt;i++)
{
sum=0;
dfs(i,a[i].left,0);
ans=(ans*sum)%mod;
for(int j=a[i].left;j<=a[i].right;j++)
{
int xx=find(e[j].op),yy=find(e[j].ed);
if(xx!=yy)f[xx]=yy;
}
}
printf("%d\n",ans);
return 0;
}
2：次小生成树
#include<cstdio>
#include<algorithm>
using namespace std;
#define R register
#define max(x,y) x>y?x:y//返回最大值
#define maxp(x,y) if(x<y)x=y;//更新最大值
#define in(z)\
while(*++p<'-');\
z=*p&15;\
while(*++p>'-')z*=10,z+=*p&15//读优
const int N=100009,M=300009;
long long sum;//注意不能开int
char s[M<<5];
bool mst[M];
int P,he[N],ne[N<<1],to[N<<1],len[N<<1],ff[N],b[N],d[N];
struct ST{
int f,m1,m2;
}st[N][18];//封起来
struct EDGE{
int u,v,l;
inline bool operator<(EDGE x)const{//用于sort
return l<x.l;
}
inline void add(){//将该边加入最小生成树
sum+=l;
to[++P]=v;ne[P]=he[u];he[u]=P;len[P]=l;
to[++P]=u;ne[P]=he[v];he[v]=P;len[P]=l;
}
}e[M];
void dfs(R int u,R int fa){//建树，预处理
d[u]=d[fa]+1;
st[u][0].f=fa;
R ST*a,*l,*r;//卡常指针,a总区间,l上区间,r下区间
//可忽略下面一行（极其丑陋）
for(R int&i=b[u];((a=&st[u][i+1])->f=(l=&st[(r=&st[u][i])->f][i])->f);++i){
if(l->m1>r->m1)a->m1=l->m1,a->m2=max(l->m2,r->m1);
else if(r->m1>l->m1)a->m1=r->m1,a->m2=max(r->m2,l->m1);
else a->m1=l->m1,a->m2=max(l->m2,r->m2);//注意认真分析最大和次大的转移
}
for(R int i=he[u];i;i=ne[i])
if(to[i]!=fa)st[to[i]][0].m1=len[i],dfs(to[i],u);
}
int getf(R int x){//并查集
if(x!=ff[x])return ff[x]=getf(ff[x]);
return x;
}
int main(){
fread(s,1,sizeof(s),stdin);//卡常
R char*p=s-1;//再卡常
R ST*l,*r;//还是卡常
R int n,m,i,j,k,x,y,now,nl,ans=2147483647;
in(n);in(m);
for(i=1;i<=m;++i){
in(e[i].u);in(e[i].v);in(e[i].l);
}
//kruscal开始
sort(e+1,e+m+1);
for(i=1;i<=n;++i)ff[i]=i;
for(i=1;P>>1<n-1;++i){
x=getf(ff[e[i].u]);y=getf(ff[e[i].v]);
if(x==y)continue;
mst[i]=1;//标记为树边
ff[x]=y;
e[i].add();
}
dfs(1,0);
for(i=1;i<=m;++i){
if(mst[i])continue;
x=e[i].u;y=e[i].v;now=0;nl=e[i].l;
//倍增，跳LCA以及更新当前最大贡献
if(d[x]<d[y])j=x,x=y,y=j;
for(j=0,k=d[x]-d[y];k;++j,k>>=1){//调整至深度相同
if(k&1){
if((l=&st[x][j])->m1!=nl){maxp(now,l->m1);}
else{maxp(now,l->m2);}
x=l->f;
}
}
if(x==y)goto F;//不用跳LCA了，下面直接跳过
for(j=b[x];j>=0;--j){
if((l=&st[x][j])->f==(r=&st[y][j])->f)continue;
if(l->m1!=nl){maxp(now,l->m1);}
else{maxp(now,l->m2);}//判断用最大还是次大更新
if(r->m1!=nl){maxp(now,r->m1);}
else{maxp(now,r->m2);}
x=l->f;y=r->f;
}
//注意下面几行，还没跳到LCA上，还要算父边有没有贡献（害我WA了N回）
if((l=&st[x][0])->m1!=nl){maxp(now,l->m1);}
else{maxp(now,l->m2);}
if((r=&st[y][0])->m1!=nl){maxp(now,r->m1);}
else{maxp(now,r->m2);}
F:if(ans>nl-now)ans=nl-now;
}
printf("%lld\n",sum+ans);
return 0;
}
3：最小生成树个数
#include<bits/stdc++.h>
using namespace std;
const int mod=31011;
struct mdzz{
int op,ed,v;
}e[1010];
struct rbq{
int left,right,va;
}a[1010];
int n,m,f[110],ans,q[110],cnt,sum,tot;
int find(int x){return x==f[x]?x:find(f[x]);}
bool cmp(mdzz a,mdzz b){
return a.v<b.v;
}
void dfs(int x,int now,int k)
{
if(now==a[x].right+1)
{
if(k==a[x].va)sum++;
return;
}
int xx=find(e[now].op),yy=find(e[now].ed);
if(xx!=yy)
{
f[xx]=yy;
dfs(x,now+1,k+1);
f[xx]=xx;f[yy]=yy;
}
dfs(x,now+1,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].op,&e[i].ed,&e[i].v);
sort(e+1,e+m+1,cmp);
int tot=0;
for(int i=1;i<=m;i++)
{
if(e[i].v!=e[i-1].v)cnt++,a[cnt].left=i,a[cnt-1].right=i-1;
int xx=find(e[i].op),yy=find(e[i].ed);
if(xx!=yy)f[xx]=yy,a[cnt].va++,tot++;
}
if(tot!=n-1){printf("0");return 0;}
a[cnt].right=m;
ans=1;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=cnt;i++)
{
sum=0;
dfs(i,a[i].left,0);
ans=(ans*sum)%mod;
for(int j=a[i].left;j<=a[i].right;j++)
{
int xx=find(e[j].op),yy=find(e[j].ed);
if(xx!=yy)f[xx]=yy;
}
}
printf("%d\n",ans);
return 0;
}