2009-3-7-tju2248.txt

MDSD算法！ 这个是我们中国人自己发现的一个算法！ 在ACM中属于比较难得题目！ 我只有有一个模板

#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAX=105;
const int INF=0x6fffffff;
//以下两个函数为MDST算法的模板！
int n,used[MAX],pass[MAX],eg[MAX],more,queue[MAX];
int g[MAX][MAX];//如果是整数将double改为int
void combine(int id,int &sum)
{
	int tot=0,from,i,j,k;
	for(;id!=0&&!pass[id];id=eg[id])
	{queue[tot++]=id;pass[id]=1;}
	for(from=0;from<tot&&queue[from]!=id;from++);
	if(from==tot)return;more=1;
	for(i=from;i<tot;i++)
	{
		sum+=g[eg[queue[i]]][queue[i]];
		if(i!=from)
		{ 
			used[queue[i]]=1;
		    for(j=1;j<=n;j++)
				if(!used[j])
			       if(g[queue[i]][j]<g[id][j])
					   g[id][j]=g[queue[i]][j];
		}
	}
	for(i=1;i<=n;i++)
		if(!used[i]&&i!=id)
		{
		  for(j=from;j<tot;j++)
		  {
			  k=queue[j];
		    if(g[i][id]>g[i][k]-g[eg[k]][k])
			   g[i][id]=g[i][k]-g[eg[k]][k];
		  }
		}
}
int MDST(int root)//return the total length of MDST
{
	int i,j,k;
	int sum=0;//如果是整数将double改为int
	memset(used,0,sizeof(used));
	for(more=1;more;)
	{
	    more=0;
	    memset(eg,0,sizeof(eg));
	    for(i=1;i<=n;i++) 
			if(!used[i]&&i!=root)
			{
		      for(j=1,k=0;j<=n;j++) 
				  if(!used[j]&&i!=j)
			         if(k==0||g[j][i]<g[k][i])
						 k=j;
	            eg[i]=k;
			}
	memset(pass,0,sizeof(pass));
	for(i=1;i<=n;i++)
		if(!used[i]&&!pass[i]&&i!=root)
			combine(i,sum);
	}
	for(i=1;i<=n;i++)
		if(!used[i]&&i!=root)
			sum+=g[eg[i]][i];
	return sum;
}
int main()
{
	int i,m,st,ed;
	int ans,distance;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		for(i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=INF;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&st,&ed,&distance);
			g[st][ed]=distance;
		}
		ans=MDST(1);
		if(ans<INF)
		   printf("%d\n",ans);
		else
			printf("impossible\n");
	}
	return 0;
}
/*
5 8
1 2 3
1 3 5
2 4 2
3 1 5
3 2 5
3 4 4
3 5 7
5 4 3
3 3
1 2 3
1 3 5
3 2 1
0 0



17
6
*/