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

};