msts.cpp

spoj MSTS kruskal +生成树

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
const int Mod = 31011;
const int Mod1 = 3;
const int Mod2 = 10337;
const double zero = 1e-5;
const int maxm = 2000;
const int maxn = 110;
typedef int Tmatrix[maxn][maxn];

int DIV1[Mod1+100],DIV2[Mod2+100];

struct Tedge {
	int x,y,c;
}edge[maxm];
bool operator < (Tedge a,Tedge b) {
	return a.c<b.c;
}

Tmatrix tg;
int n,m,nn,tnn,ans;
int list[maxn],tot;
int added[maxn];//�Ƿ��ڴ˴εı߼���;
int mark[maxn],vis[maxn];	//mark ������ͼ�ı��� vis dfs�Ƿ�������
int pos[maxn];//ԭ�����Ӧg�еĵ�

struct GraphType {
	int a[maxn][maxn];
	int n,M;
	void makematrix(int nodes[],int tot) {
		n=tot;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				a[i][j]=0;
		for (int i=1;i<=n;i++)	{
			for (int j=1;j<=n;j++)
				if (i!=j) 
					if (tg[nodes[i]][nodes[j]]) {
						a[i][j]=M-tg[nodes[i]][nodes[j]];
						a[i][i]+=tg[nodes[i]][nodes[j]];
					}
			a[i][i]%=M;
		}
	}
	inline	int getdiv(int x) {
		if (M==Mod1) return DIV1[x]; else return DIV2[x];
	}
	inline int Mul(int x,int y) {
		return (x*y)%M;
	}
	int DET() {
		n--;
		int ret=1;
		for (int i=1;i<=n;i++) {
			int k;
			k=-1;
			for (int j=i;j<=n;j++)
				if (a[j][i]>0) { k=j;break; }
			if (k==-1) return 0;
			if (k!=i) {
				for (int o=1;o<=n;o++) {
					int t;
					t=a[i][o];a[i][o]=a[k][o];a[k][o]=t;
				}
				ret=(ret*(M-1))%M;
			}
			for (int j=i+1;j<=n;j++) {
					for (int o=i+1;o<=n;o++)
						a[j][o]=(a[j][o]-Mul(Mul(a[j][i],getdiv(a[i][i])),a[i][o])+M)%M;
					a[j][i]=0;
				}
		}
		for (int i=1;i<=n;i++)
			ret=(ret*a[i][i])%M;
		return ret;
	}
	void dump() {
		printf("---dump---\n");
		for (int i=1;i<=n;i++)	{
			for (int j=1;j<=n;j++)
				printf("%d ",a[i][j]);
				printf("\n");
			}
		printf("---dump---\n");
	}
}G1,G2;

void push_node(int x,int y) {
	if (!added[x]) 		added[x]=1;
	if (!added[y])		added[y]=1;
	tg[x][y]++;tg[y][x]++;
}

void dfs_find(int x,int id) {
	vis[x]=1;
	mark[x]=id;
	list[++tot]=x;
	for (int y=1;y<=n;y++)
		if (!vis[y]&&added[y]&&tg[x][y])
			dfs_find(y,id);
}

int expMod(int a,int e,int M) {
	if (e==0) return 1;
	if (e==1) return a;
	int t=expMod(a,e/2,M);
	t=(t*t)%M;
	if (e%2==1) t=(t*a)%M;
	return t;
}

void init() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) {		
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		edge[i].x=x;edge[i].y=y;edge[i].c=c;
	}
	sort(edge+1,edge+1+m);
}

void prepare() {
	for (int i=0;i<Mod1;i++) DIV1[i]=expMod(i,Mod1-2,Mod1);
	for (int i=0;i<Mod2;i++) DIV2[i]=expMod(i,Mod2-2,Mod2);
}

int GetMod(int a,int b) {
	return ((a*20674)%Mod+(b*10338)%Mod)%Mod;
}

void work() {
	for (int i=1;i<=n;i++) pos[i]=i;
	G1.M=Mod1;G2.M=Mod2;
	ans=1;nn=n;
	for (int ei=1;ei<=m;) {
		int nowcost=edge[ei].c;
		memset(tg,0,sizeof(tg));
		memset(added,0,sizeof(added));
		for (;ei<=m&&edge[ei].c==nowcost;ei++)
			if (pos[edge[ei].x]!=pos[edge[ei].y])
				push_node(pos[edge[ei].x],pos[edge[ei].y]);

		memset(vis,0,sizeof(vis));
		tnn=0;
		for (int i=1;i<=nn;i++) 
			if (!vis[i]) {
				if (!added[i])	{
					mark[i]=++tnn;
					vis[i]=1;
				}
				else {
					tnn++;
					tot=0;
					dfs_find(i,tnn);
					G1.makematrix(list,tot);
					G2.makematrix(list,tot);
					int t1=G1.DET(),t2=G2.DET();
					ans=(ans*GetMod(t1,t2))%Mod;
				}
			}
		//build a new graph
		for (int i=1;i<=n;i++)
			pos[i]=mark[pos[i]];
		nn=tnn;
	}
	printf("%d\n",ans);
}

int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	init();
	prepare();
	work();
	return 0;
}