既见君子

同济医学生的起落落落落人生记录

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();
}

评论
©既见君子
Powered by LOFTER