読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0072 : Carden Lantern

404 Not Found

Prim法(全域最小木) + オマケに植木算。以前やったウォーターデブンのソースと似た感じ。

#include <iostream>
#include <set>
#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MP(a,b) make_pair(a,b)
int main(){
	int n,m,a,b,c,mi,ret;
	int info[100][100];
	pair<int,int> now;
	while(cin >> n && n){
		cin >> m;
		ret = 0;
		rep(i,100)rep(j,100)info[i][j] = INT_MAX;

		rep(i,m){
			scanf("%d,%d,%d\n",&a,&b,&c);
			info[a][b] = info[b][a] = (c/100)-1;
		}

		set<int> remain;
		for(int i=1;i<n;i++)remain.insert(i);

		while(!remain.empty()){
			now = MP(1<<21,-1);
			rep(i,n)
			  if(remain.find(i) == remain.end() )
			    rep(j,n)
			      if(remain.find(j) != remain.end())now = min(now,MP(info[i][j],j));
			ret+=now.first;
			remain.erase(now.second);
		}
		cout << ret << endl;
	}
}