TopCoder SRM 539 Div1 Medium SafeReturn

これも割とすんなり。
http://community.topcoder.com/stat?c=problem_statement&pm=11805

問題

N頂点からなる距離付無向グラフが与えられる。
初期状態で0番の頂点にN人の兵士がいるので、0～(N-1)番の頂点に１人ずつ配備したい。

各兵士は目的の頂点に対し最短距離で移動しなければならないが、最短距離の経路が複数あるならどれを選んでも良い。
ただし、兵士が頂点の間の辺を１人で移動すると、その兵士は危険にさらされる。

危険にさらされる兵士数を最小化するように兵士を移動させ、その兵士数を答えよ。

解法

頂点Aに行く兵士がいる場合、頂点Aを経由して頂点Bに行ける兵士がいれば、前者の兵士は危険にさらされずに済む。
よって、この依存関係をグラフで表し、最大マッチングを求めればよい。

以下のコードでは、Warshall-Floyd法で経由しうる頂点を求め、最大フローで最大マッチング数を求めている。

なお、１人で複数人を保護するケースは考えなくてよい。
例えば、0→A→B→Cという経路があれば、Cに行く兵士がBに行く兵士を守り、Bに行く兵士がAに行く兵士を守ると考えればよく、１人は目的地の直前に到達する頂点に行く兵士だけを気にすればよい。

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 1000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


class SafeReturn {
	public:
	int N,T;
	int mat[51][51];
	int minRisk(int N, vector <string> streets) {
		this->N=N;
		T=streets.size();
		
		int i,x,y;
		FOR(x,T) FOR(y,T) mat[x][y]=(streets[x][y]=='-')?1000:(streets[x][y]-'0');
		FOR(i,T) FOR(x,T) FOR(y,T) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		MaxFlow mf;
		FOR(x,N) mf.add_edge(0,10+x,1);
		FOR(x,N) mf.add_edge(100+x,1,1);
		FOR(x,N) FOR(y,N) if(mat[0][x+1]+mat[x+1][y+1]==mat[0][y+1]) mf.add_edge(10+x,100+y,1);
		return N-mf.maxflow(0,1);
	}
}

まとめ

これもすんなり。
こういううまくグラフを作れるとあっさり解ける問題はいいな。