AOJ 0180 Stellar Performance of the Debunkey Family

404 Not Found

Prim法(全域最小木)そのまま。前知ったアルゴリズム。

非常に単純で、『プリム法（最小全域木問題）』を読めば単純明快です。

ノード情報は隣接行列で実装。

#include <iostream>
#include <list>
#include <algorithm>
#include <climits>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n,m,a,b,c,mi,ret;
	int info[100][100];

	while(cin >> n >> m && n){
		ret = 0;
		rep(i,100)rep(j,100)info[i][j] = INT_MAX;

		rep(i,m){
			cin >> a >> b >> c;
			info[a][b] = info[b][a] = c;
		}

		list<int> X,Y;
		X.push_back(0);
		for(int i=1;i<n;i++){
			Y.push_back(i);
		}

		while(!Y.empty()){
			mi = INT_MAX;
			for(list<int>::iterator it = X.begin(); it != X.end(); ++it){
				rep(i,n){
					if( count(Y.begin(),Y.end(),i) ){
						if(info[*it][i]<mi){
							a = i;
							mi = info[*it][i];
						}
					}
				}
			}
			X.push_back(a);
			for(list<int>::iterator it = Y.begin(); it != Y.end(); ++it){
				if((*it)==a){
					Y.erase(it);
					break;
				}
			}
			ret+=mi;
		}
		cout << ret << endl;
	}
}