SRM 539 550pt : SafeReturn
問題概要
兵士がN(<50)人城0にいる。城1~V(N
解法
実はこのままではこの問題は解けず、「合流はない」という条件を付け加えなければならない。
最短経路に使われる辺だけを(有向化して)残すと辺の重みが正なのでDAGになる(距離の近い順がそのままトポロジカル順序になっている)。求めるのはこのDAGでの最小パス被覆。典型問題で、二部マッチングを使って解ける。
acceptされたコード
#include <algorithm> #include <cstring> #include <vector> #include <string> using namespace std; const int MAX_N = 50; struct BipartiteMatching{ static const int MAX_V = ::MAX_N * 2; int V; vector<int> graph[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void clear(){ for(int i=0; i<MAX_V; i++){ graph[i].clear(); } } void add_edge(int u, int v){ graph[v].push_back(u); graph[u].push_back(v); } bool dfs(int v){ used[v] = true; for(int i=0; i<(int)graph[v].size(); i++){ int u = graph[v][i], w = match[u]; if(w<0 || (!used[w] && dfs(w)) ){ match[v] = u; match[u] = v; return true; } } return false; } int bipartite_matching(){ int ret = 0; memset(match, -1, sizeof(match)); for(int v=0; v<V; v++){ if(match[v] < 0){ memset(used, 0, sizeof(used)); if(dfs(v)){ ret++; } } } return ret; } void set_V(int V_){ V = V_; } }; BipartiteMatching bm; const int INF = 1<<29; int graph[MAX_N][MAX_N]; struct SafeReturn { int minRisk(int N, vector <string> streets) { const int M = streets.size(); for(int i=0; i<M; i++){ fill(graph[i], graph[i] + M, INF); } //build graph for(int i=0; i<M; i++){ for(int j=0; j<M; j++){ if(streets[i][j] != '-'){ graph[i][j] = streets[i][j]&15; } } } //WF for(int k=0; k<M; ++k){ graph[k][k] = 0; for(int i=0; i<M; ++i){ for(int j=0; j<M; ++j){ graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } } } //build dag N++; bm.set_V(2 * N); for(int i=0; i<N; i++){ for(int j=0; j<N; j++)if(i!=j){ for(int k=0; k<N; k++){ if(graph[0][j] == graph[0][i] + graph[i][j]){ bm.add_edge(i, j+N); break; } } } } //return dag min path cover return N - bm.bipartite_matching(); } };