LightOJ1029-Civil and Evil Engineer-生成树

题目大意：给你一张图，求它的最小生成树和最大生成树的的总费用/2；

题目解析： 用prime算法即可，求最小生成树的时候，只要每次取出长度当前长度最小的那条边，并且维护dist[]就可以了，因为是树状结构，肯定不会有环，最大生成树也是类似；

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int inf=0x3fffffff;
int graph1[110][110],graph2[110][110],dist[110],n;
bool vis[110];
int min_prime()
{
	int sum=0,i,j,k,temp;
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	for(i=1;i<=n;i++)
	{
		dist[i]=graph1[0][i];
	}
	for(k=1;k<=n;k++)
	{
		temp=inf;
		j=-1;
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&dist[i]<temp)
			{
				temp=dist[i];
				j=i;
			}
		}
		if(j==-1)
			return sum;
		sum+=temp;
		vis[j]=1; 
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&dist[i]>graph1[j][i])
			{
				dist[i]=graph1[j][i];
			}
		}
	}
	return sum;
}
int max_prime()
{
	int sum=0,i,j,k,temp;
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	for(i=1;i<=n;i++)
	{
		dist[i]=graph2[0][i];
	}
	for(k=1;k<=n;k++)
	{
		temp=0;
		j=-1;
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&dist[i]>temp)
			{
				temp=dist[i];
				j=i;
			}
		}
		if(j==-1)
			return sum;
		sum+=temp;
		vis[j]=1; 
		for(i=1;i<=n;i++)
		{
			if(!vis[i]&&dist[i]<graph2[j][i])
			{
				dist[i]=graph2[j][i];
			}
		}
	}
	return sum;
}
int main()
{
	int cas,c,u,v,w,i,j;
	scanf("%d",&cas);
	for(c=1;c<=cas;c++)
	{
		memset(graph2,0,sizeof(graph1));
		for(i=0;i<110;i++)
			for(j=0;j<110;j++)
				graph1[i][j]=inf;
		scanf("%d",&n);
		while(scanf("%d%d%d",&u,&v,&w)&&(u+v+w)!=0)
		{
			graph1[v][u]=graph1[u][v]=min(w,graph1[u][v]);
			graph2[v][u]=graph2[u][v]=max(w,graph2[u][v]);
		}
		int min_cost=min_prime();
		int max_cost=max_prime();
		if((max_cost+min_cost)%2==1)
			printf("Case %d: %d/2\n",c,max_cost+min_cost);
		else 
			printf("Case %d: %d\n",c,(max_cost+min_cost)/2);
	} 
	return 0;
}