SRM328 div1 medium

TopCoder Statistics
↑のテキトー日本語訳
最終的にグラフはそれぞれに一つずつmarkedを含む部分グラフに分けられる。
markedな頂点A,B(AとBの間には他のmarkedな頂点はない)を考える。
AとBを分けるときに使う辺はAとBの間で最もコストの小さい辺である。

#include <string>
#include <vector>
#include <sstream>

using namespace std;

int occupied[50];
int cost[50][50];
int INF=(1<<28);

class BlockEnemy 
{
	public:

		int N;

		bool DFS(int here,int from)
		{
			if(occupied[here])
				return true;
			for(int to=0;to<N;to++)
				if(to!=from && cost[here][to]!=INF && DFS(to,here))
					return true;
			return false;
		}

		int minEffort(int _N, vector <string> roads, vector <int> occupiedTowns) 
		{
			N=_N;

			int rN=roads.size();
			vector<int> a(rN),b(rN),e(rN);
			for(int i=0;i<N;i++)
				for(int j=0;j<N;j++)
					cost[i][j]=INF;
			for(int i=0;i<rN;i++)
			{
				stringstream ss(roads[i]);
				ss >> a[i] >> b[i] >> e[i];
				cost[a[i]][b[i]]=cost[b[i]][a[i]]=e[i];
			}
			for(int i=0;i<rN;i++)
				for(int j=i+1;j<rN;j++)
					if(e[j]<e[i])
						swap(a[i],a[j]),swap(b[i],b[j]),swap(e[i],e[j]);
			
			for(int i=0;i<N;i++)
				occupied[i]=false;
			for(int i=0;i<occupiedTowns.size();i++)
				occupied[occupiedTowns[i]]=true;

			int ans=0;
			for(int i=0;i<rN;i++)
				if(DFS(a[i],b[i]) && DFS(b[i],a[i]))
					ans+=e[i],cost[a[i]][b[i]]=cost[b[i]][a[i]]=INF;

			return ans;
		}
};