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; } };