BZOJ 1016 最小生成树计数
其实这道题某韩老师来讲课的时候考过，没调出来耿耿于怀，现在终于A啦撒花。哎果然还是太弱了看了一发韩老师的标程只有70行，我就高消就写了70行，感叹世事沧桑阿- -
/*------------------
最小生成树计数问题
MST+matrix_tree
考虑到对于每一种权值，树的连通性固定，所以分阶段用matrix_tree处理。
然后模数不为质，辗转相除求行列式
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
using namespace std;
const int INF=1000+5;
struct edge{
int x,y,val;
} e[10000+5];
typedef pair<int,int> pr;
vector <pr> G[INF];
bool vis[INF];
int n,m,f[INF],cnt,s[INF],st[INF],en[INF],a[INF][INF],mod=31011,id[INF];
bool cmp(edge a,edge b){
return a.val<b.val;
}
void together(int a,int b);
void pre(){
cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) f[i]=s[i]=i;
for(int i=1;i<=m;++i) {
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val);
together(e[i].x,e[i].y);
}
sort(e+1,e+m+1,cmp);
e[0].val=0;
for(int i=1;i<=m;++i)
if(e[i].val!=e[i-1].val){
cnt++;
st[cnt]=i;
en[cnt-1]=i-1;
}
if(!en[cnt]) en[cnt]=m;
}
int gauss(int x){
for(int i=1;i<=x;++i)
for(int j=1;j<=x;++j)
{ a[i][j]%=mod;
if(a[i][j]<0) a[i][j]+=mod;
//cout<<a[i][j]<<endl;
}
/*for(int i=1;i<=x;++i){
for(int j=1;j<=x;++j)
printf("%d ",a[i][j]);
printf("\n");
}*/
int ans=1;
for(int i=1;i<=x;++i){
int j;
for(j=i;j<=x;++j) if(a[j][i]) break;
if(j!=i) {
ans*=-1;
for(int k=1;k<=x;++k) swap(a[i][k],a[j][k]);
}
for(j=i+1;j<=x;++j){
while(a[j][i]){
int tmp1=a[i][i],tmp2=a[j][i];
if(tmp1>tmp2){
int p=tmp1/tmp2;
if(tmp1%tmp2==0) p--;
for(int k=1;k<=x;++k)
{
a[i][k]-=((long long)p*a[j][k])%mod;
a[i][k]%=mod;
if(a[i][k]<0) a[i][k]+=mod;
// printf("%d ",a[i][k]);
}
// printf("\n");
}
else {
int p=tmp2/tmp1;
for(int k=1;k<=x;++k){
a[j][k]-=((long long)p*a[i][k])%mod;
a[j][k]%=mod;
if(a[j][k]<0) a[j][k]+=mod;
// printf("%d ",a[j][k]);
}
// printf("\n");
}
}
}
ans=((long long)ans*(long long)a[i][i])%mod;
if(ans<0) ans+=mod;
}
return ans;
}
int depsolve(int now){
int id_cnt=0;
memset(id,0,sizeof(id));
for(int i=0;i<G[now].size();++i){
int x=G[now][i].first,y=G[now][i].second;
if(!id[x]) id[x]=++id_cnt;
if(!id[y]) id[y]=++id_cnt;
}
for(int i=1;i<=id_cnt;++i)
for(int j=1;j<=id_cnt;++j)
a[i][j]=0;
for(int i=0;i<G[now].size();++i){
int x=G[now][i].first,y=G[now][i].second;
// cout<<now<<" "<<x<<" "<<y<<endl;
x=id[x],y=id[y];
a[x][y]--;
a[y][x]--;
a[x][x]++;
a[y][y]++;
}
G[now].clear();
return gauss(id_cnt-1);
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int sfa(int x){
return x==s[x]?x:s[x]=sfa(s[x]);
}
void stogether(int x,int y){
x=sfa(x);
y=sfa(y);
if(x!=y) s[x]=y;
}
void together(int x,int y){
x=find(x);
y=find(y);
if(x!=y) f[x]=y;
}
void solve(){
long long ans=1;
/*for(int i=1;i<=cnt;++i)
printf("%d %d %d\n",i,st[i],en[i]);*/
for(int i=1;i<=cnt;++i){
for(int j=st[i];j<=en[i];++j){
if(find(e[j].x)==find(e[j].y)) continue;
stogether(e[j].x,e[j].y);
//cout<<sfa(e[j].x)<<" "<<sfa(e[j].y)<<endl;
}
for(int j=st[i];j<=en[i];++j){
if(find(e[j].x)==find(e[j].y)) continue;
int fa=sfa(e[j].x);
//cout<<fa<<endl;
G[fa].push_back(make_pair(find(e[j].x),find(e[j].y)));
}
for(int j=st[i];j<=en[i];++j){
if(find(e[j].x)==find(e[j].y)) continue;
int fa=sfa(e[j].x);
if(G[fa].size()) ans*=depsolve(fa),ans%=mod;
}
for(int j=st[i];j<=en[i];++j)
together(e[j].x,e[j].y);
}
printf("%d\n",(int)ans);
}
int main(){
freopen("MST.in","r",stdin);
pre();
for(int i=2;i<=n;++i) if(find(i)!=find(i-1)){
printf("0\n");
return 0;
}//bzoj上没保证图是联通的所以就错在这里了，一直0msWA把我吓惨了
for(int i=1;i<=n;++i) f[i]=i;
solve();
}