SRM 539 DIV1 Medium SafeReturn

http://apps.topcoder.com/stat?c=problem_statement&pm=11805&rd=14731
追記: (コメント/Editorialより) 想定解(とこの解答)は間違っているらしい
Editorial読んでたのに、そのことに気づかない程度の英語力！

問題

N(1<=N<=49)人の兵士がいて、T(N+1<=T<=50)つの砦がある。
i番目の兵士は砦0から砦iへ向かいたい。
砦同士の道は距離(INFか1〜9)があり、全ての兵士は最小距離で目指す砦へつ行き、そのあとはそこにとどまる。
しかし、道は危険であり、兵士が一人だけで道を通る(危険に晒される)ことはあまりしたくなく、危険に晒される兵士の数をできるだけ少なくしたい。
危険に晒される兵士の数の最小値を求めろ

回答

まず、兵士が二人以上でいるということは、片方の兵士の砦へつくまでもう一人がずっと付き添っており、そのあと自分の砦へ向かう。ということのみである。(ここがあまりわかってない)
http://d.hatena.ne.jp/anta1/20120816/1345046832に書いたが、それをグラフにするとDAGとなり、問題はその最小パス被覆を求める問題となり、二部マッチングする。

コメント

現在もあまりよくわかってない。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof(o.begin()) it = o.begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;

vector<bool> done;
vector<int> match;
vector<vector<int> >e;
bool augment(int i) {
	if(done[i]) return false;
	else done[i] = true;
	each(j, e[i]) if(match[*j] == -1 || augment(match[*j])) {
		match[*j] = i;
		return true;
	}
	return false;
}

struct SafeReturn {
	int minRisk(int N, vector <string> streets) {
		int n = streets.size();
		static int wf[51][51];
		rep(i, n) rep(j, n) wf[i][j] = streets[i][j] == '-' ? (int)INF : streets[i][j] - '0';
		rep(i, n) wf[i][i] = 0;
		rep(k, n) rep(i, n) rep(j, n) {
			if(wf[i][k] != INF && wf[k][j] != INF)
				wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
		}
		e = vector<vector<int> >(N);
		rep(i, N) rep(j, N) if(i != j && wf[0][i+1] + wf[i+1][j+1] == wf[0][j+1]) e[i].pb(j);
		match = vector<int>(N, -1);
		int count = 0;
		rep(i, N) {
			done = vector<bool>(N, false);
			if(augment(i)) ++ count;
		}
		return N - count;
	}
};