首页 > ACM题库 > HDU-杭电 > HDU 4408-Minimum Spanning Tree-图-[解题报告]HOJ
2015
07-16

HDU 4408-Minimum Spanning Tree-图-[解题报告]HOJ

Minimum Spanning Tree

问题描述 :

XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertexes and m (0<=m<=1000) edges, he wants to know the number of minimum spanning trees in the graph.

输入:

There are no more than 15 cases. The input ends by 0 0 0.
For each case, the first line begins with three integers — the above mentioned n, m, and p. The meaning of p will be explained later. Each the following m lines contains three integers u, v, w (1<=w<=10), which describes that there is an edge weighted w between vertex u and vertex v( all vertex are numbered for 1 to n) . It is guaranteed that there are no multiple edges and no loops in the graph.

输出:

There are no more than 15 cases. The input ends by 0 0 0.
For each case, the first line begins with three integers — the above mentioned n, m, and p. The meaning of p will be explained later. Each the following m lines contains three integers u, v, w (1<=w<=10), which describes that there is an edge weighted w between vertex u and vertex v( all vertex are numbered for 1 to n) . It is guaranteed that there are no multiple edges and no loops in the graph.

样例输入:

5 10 12
2 5 3
2 4 2
3 1 3
3 4 2
1 2 3
5 4 3
5 1 3
4 1 1
5 3 3
3 2 3
0 0 0

样例输出:

4

http://acm.hdu.edu.cn/showproblem.php?pid=4408

题意:求最小生成树的个数

#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define N 105
#define M 1005
#define E
#define inf 0x3f3f3f3f
#define dinf 1e10
#define linf (LL)1<<60
#define LL long long
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;


int mod;
struct Edge
{
    int a,b,c;
    bool operator<(const Edge & t)const
    {
        return c<t.c;
    }
} edge[M];
int n,m;
long long ans;
int fa[N],ka[N],vis[N];//fa,ka都是并查集,ka是每组边临时使用
LL gk[N][N],tmp[N][N];//gk顶点之间的关系,tmp为生成树计数用的矩阵
vector<int>gra[N];


int findfa(int a,int b[])
{
    return a==b[a]?a:b[a]=findfa(b[a],b);
}


LL det(LL a[][N],int n)//生成树计数
{
    for(int i=0; i<n; i++)for(int j=0; j<n; j++)a[i][j]%=mod;
    long long ret=1;
    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
            while(a[j][i])
            {
                LL t=a[i][i]/a[j][i];
                for(int k=i; k<n; k++)
                    a[i][k]=(a[i][k]-a[j][k]*t)%mod;
                for(int k=i; k<n; k++)
                    swap(a[i][k],a[j][k]);
                ret=-ret;
            }
        if(a[i][i]==0)return 0;
        ret=ret*a[i][i]%mod;
    }
    return (ret+mod)%mod;
}


int main()
{
    //freopen("/home/axorb/in","r",stdin);
    while (scanf("%d%d%d",&n,&m,&mod),n+m+mod)
    {
        memset(gk,0,sizeof(gk));
        for(int i=1;i<=n;i++)
            gra[i].clear();
        for(int i=0; i<m; i++)
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
        sort(edge,edge+m);
        for(int i=1; i<=n; i++)fa[i]=i,vis[i]=0;
        int pre=-1;
        ans=1;
        for(int h=0; h<=m; h++)
        {
            if(edge[h].c!=pre||h==m)//一组边加完
            {
                for(int i=1; i<=n; i++)
                    if(vis[i])
                    {
                        int u=findfa(i,ka);
                        gra[u].push_back(i);
                        vis[i]=0;
                    }
                for(int i=1; i<=n; i++) //枚举每个联通分量
                    if(gra[i].size()>1)
                    {
                        for(int a=1; a<=n; a++)
                            for(int b=1; b<=n; b++)
                                tmp[a][b]=0;
                        int len=gra[i].size();
                        for(int a=0; a<len; a++) //构建矩阵
                            for(int b=a+1; b<len; b++)
                            {
                                int la=gra[i][a],lb=gra[i][b];
                                tmp[a][b]=(tmp[b][a]-=gk[la][lb]);
                                tmp[a][a]+=gk[la][lb];
                                tmp[b][b]+=gk[la][lb];
                            }
                        int ret=(int)det(tmp,len);
                        ans=(ans*ret)%mod;
                        for(int a=0; a<len; a++)fa[gra[i][a]]=i;
                    }
                for(int i=1; i<=n; i++)
                {
                    ka[i]=fa[i]=findfa(i,fa);
                    gra[i].clear();
                }
                if(h==m)break;
                pre=edge[h].c;
            }
            int a=edge[h].a,b=edge[h].b;
            int pa=findfa(a,fa),pb=findfa(b,fa);
            if(pa==pb)continue;
            vis[pa]=vis[pb]=1;
            ka[findfa(pa,ka)]=findfa(pb,ka);
            gk[pa][pb]++;
            gk[pb][pa]++;
        }
        int flag=0;
        for(int i=2; i<=n&&!flag; i++)if(ka[i]!=ka[i-1])flag=1;
        if(m==0)
            flag=1;
        printf("%I64d\n",flag?0:ans%mod);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xdu_truth/article/details/8010308