学步园

HDOJ 1233 还是畅通工程

/*
HDOJ 1233 还是畅通工程
简单的MST就行了
*/

#include <iostream>
using namespace std;

#define INF 99999999

int graph[103][103];
int sum,N;

void Prim(int v)
{
	int lowcast[103];
	int i,min,j,k;

	for(i=1;i<=N;i++)
	{
		lowcast[i]=graph[v][i];
	}

	lowcast[v]=0;

	for(i=1;i<=N;i++)
	{
		min=INF;
		for(j=1;j<=N;j++)
		{
			if(lowcast[j]!=0 && lowcast[j]<min)
			{
				min=lowcast[j];
				k=j;
			}
		}
		lowcast[k]=0;
		if(min == INF)
			return;
		sum += min;
		
		for(j=1;j<=N;j++)
		{
			if(graph[k][j]<lowcast[j])
			{
				lowcast[j]=graph[k][j];
			}
		}
	}
}

void Create_Graph()
{
	int m=N*(N-1)/2;
	int i,j,a,b,w;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			graph[i][j]=INF;
		}
	}

	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>w;
		graph[a][b]=w;
		graph[b][a]=w;
	}
}

int main()
{
	while(cin>>N)
	{
		if(N == 0)
			break;
		sum=0;
		Create_Graph();
		Prim(1);
		cout<<sum<<endl;
	}
	return 0;
}

HDOJ 1863 畅通工程

/*
HDOJ 1863 畅通工程
MST简单应用
*/

#include <iostream>
#include <algorithm>
using namespace std;

struct edge
{
	int a;
	int b;
	int cost;
}c[2000];

int p[103];
int rank[103];
int N,M;

bool cmp(const edge &a,const edge &b)
{
	return (a.cost<b.cost);
}

int Find(int x)
{
	int y,root,w;
	y=x;
	while(p[y] != y)
		y=p[y];
	root=y;
	y=x;
	while(p[y] != y)
	{
		w=p[y];
		p[y]=root;
		y=w;
	}
	return root;
}

void Union(int a,int b)
{
	if(rank[a] <= rank[b])
	{
		p[a]=b;
		if(rank[a] == rank[b])
			++rank[b];
	}
	else
		p[b]=a;
}

void Make_set()
{
	for(int i=1;i<=M;i++)
	{
		p[i]=i;
		rank[i]=0;
	}
}

int main()
{
	int i,j,sum,count,x,y;
	while(cin>>N>>M)
	{	
		if(N == 0)
			break;
		Make_set();
		for(i=0;i<N;i++)
			cin>>c[i].a>>c[i].b>>c[i].cost;
		sort(c,c+N,cmp);
		sum=0;
		count=0;
		for(i=0;i<N;i++)
		{
			x=Find(c[i].a);
			y=Find(c[i].b);
			if(x != y)
			{
				Union(x,y);
				count++;
				sum += c[i].cost;
			}
			if(count == M-1)
				break;
		}
		if(count == M-1)
			cout<<sum<<endl;
		else
			cout<<'?'<<endl;
	}
	return 0;
}

HDOJ 1879 继续畅通工程

/*
HDOJ 1879 继续畅通工程
MST基本运用
*/

#include <iostream>
#include <algorithm>
using namespace std;

struct edge
{
	int a;
	int b;
	int cost;
}ed[5000];

int rank[101];
int p[101];
int N,M;

bool cmp(edge &a,edge &b)
{
	return (a.cost<b.cost);
}

int Find(int x)
{
	int y,root,w;
	y=x;
	while(p[y] != y)
		y=p[y];
	root=y;
	y=x;
	while(p[y] != y)
	{
		w=p[y];
		p[y]=root;
		y=w;
	}
	return root;
}

void Union(int a,int b)
{
	if(rank[a] <= rank[b])
	{
		p[a]=b;
		if(rank[a] == rank[b])
			++rank[b];
	}
	else
		p[b]=a;
}

void Make_set()
{
	for(int i=1;i<=N;i++)
	{
		p[i]=i;
		rank[i]=0;
	}
}

int main()
{
	int i,j,count,sum,flag,num,a,b;
	edge temp;
	while(cin>>N)
	{
		Make_set();
		if(N == 0)
			break;
		M=N*(N-1)/2;
		count=0;
		num=0;
		for(i=0;i<M;i++)
		{
			cin>>temp.a>>temp.b>>temp.cost>>flag;
			if(flag == 0)
				ed[num++]=temp;
			else
			{
				a=Find(temp.a);
				b=Find(temp.b);
				if(a != b)
				{
					Union(a,b);
					count++;
				}
			}
		}
		sort(ed,ed+num,cmp);
		sum=0;
		for(i=0;i<num;i++)
		{
			a=Find(ed[i].a);
			b=Find(ed[i].b);
			if(a != b)	
			{
				Union(a,b);
				count++;
				sum += ed[i].cost;
			}
			if(count == N-1)
				break;
		}
		cout<<sum<<endl;
	}
	return 0;
}