HDU-1301 Jungle Roads(最小生成ツリーの問題)

原題リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1301
サンプル:

Sample Input
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
 

Sample Output
216
30

題意:与えられた村の数n、一連の村の間の道路は毎月コスト情報を維持し、すべての村を連通させるために最小限のメンテナンスが必要なコストを計算させる.
问题解决の考え方:この问题の特别な地方は村がアルファベットを利用して番号をつけているが、まだ顺番なので、ASCIIコードの値を利用して数字の番号に変换することができて、その他はテンプレートによって書けばいいので、Primアルゴリズムを使うことに注意して重辺を考えて、私达は具体的にコードを见ます.ここではPrimアルゴリズムとKruskalアルゴリズムの解説ブログを指します.(リンクをクリックしてください)
PrimアルゴリズムACコード:

/*
*  ：[email protected]
*blog:https://me.csdn.net/hzf0701
* ：                  ，    。
*
*/
#include	//POJ   

#define rep(i,a,n) for (int i=a;i<=n;i++)//i     ，a    ，n    ，  
#define per(i,a,n) for (int i=a;i>=n;i--)//i     ， a    ，n    ，  。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//   
const int maxn = 29;//   。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************   ，          ***************************************//

int graph[maxn][maxn];
int dis[maxn];//         。
bool vis[maxn];//           。
int n,t,w;
char ch1,ch2;
void Prim(){
	//      0   。
	vis[0]=true;
	rep(i,1,n-1){
		dis[i]=graph[0][i];
	}
	int minn,pos,sum=0;
	rep(i,1,n-1){
		minn=inf;
		rep(j,1,n-1){
			if(!vis[j]&&dis[j]<minn){
				minn=dis[j];
				pos=j;
			}
		}
		if(minn==inf)break;
		vis[pos]=true;
		sum+=minn;
		rep(j,1,n-1){
			if(!vis[j]&&dis[j]>graph[pos][j])
				dis[j]=graph[pos][j];
		}
	}
	cout<<sum<<endl;
}
int main(){
	//freopen("in.txt", "r", stdin);//         
	IOS;
	while(cin>>n&&n){
		memset(graph,inf,sizeof(graph));
		memset(vis,false,sizeof(vis));
		rep(i,0,n-2){
			cin>>ch1>>t;
			rep(j,0,t-1){
				cin>>ch2>>w;
				graph[ch2-'A'][ch1-'A']=graph[ch1-'A'][ch2-'A']=min(graph[ch2-'A'][ch1-'A'],w);
			}
		}
		Prim();
	}
	return 0;
}

KruskalアルゴリズムACコード:

/*
*  ：[email protected]
*blog:https://me.csdn.net/hzf0701
* ：                  ，    。
*
*/
#include	//POJ   

#define rep(i,a,n) for (int i=a;i<=n;i++)//i     ，a    ，n    ，  
#define per(i,a,n) for (int i=a;i>=n;i--)//i     ， a    ，n    ，  。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//   
const int maxn = 1e5;//   。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************   ，          ***************************************//

struct Edge{
	int u,v;//      。
	int w;//        。
	bool operator <(const Edge &a){
		//     。
		return w<a.w;
	}
};
Edge edges[maxn];
int n,cnt,temp1,temp2;//n   ，cnt     ，   。
int father[maxn];//father[i]   i          。
int Find(int x){
	int r=x;
	while(r!=father[r])
		r=father[r];
	int i=x,j;
	while(father[i]!=r){
		j=father[i];
		father[i]=r;
		i=j;
	}
	return r;
}
void Kruskal(){
	sort(edges,edges+cnt);
	rep(i,0,n-1)father[i]=i;
	int sum=0;
	rep(i,0,cnt-1){
		temp1=Find(edges[i].u);
		temp2=Find(edges[i].v);
		if(temp1!=temp2){
			father[temp1]=temp2;
			sum+=edges[i].w;
		}
	}
	cout<<sum<<endl;
}
char ch1,ch2;
int main(){
	//freopen("in.txt", "r", stdin);//         
	IOS;
	while(cin>>n&&n){
		cnt=0;
		rep(i,0,n-2){
			cin>>ch1>>temp1;
			rep(j,0,temp1-1){
				cin>>ch2>>temp2;
				edges[cnt].u=ch1-'A';edges[cnt].v=ch2-'A';edges[cnt].w=temp2;
				cnt++;
			}
		}
		Kruskal();
	}
	return 0;
}