にぶたんして最大流流す。
にぶたんの初期値を小さくしすぎてWA出した…
struct edge {int to, cap, rev; }; vector<edge> G[MAX_N]; bool used[MAX_N]; void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } int dfs(int v, int t, int f) { if(v == t) return f; used[v] = true; for(int i = 0; i < (int)G[v].size(); i++) { edge &e = G[v][i]; if(!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } ll max_flow(int s, int t) { ll flow = 0; while(true) { memset(used, 0, sizeof(used)); int f = dfs(s, t, inf); if(f == 0) return flow; flow += f; } } int K, C, M; //machine, cow int D[250][250]; bool ok(int m) { memset(used, 0, sizeof(used)); rep(i, 0, K + C + 2) { G[i].clear(); } int s = K + C, t = K + C + 1; rep(i, K, K + C) { rep(j, 0, K) { if(D[i][j] <= m) { //debug(m, i, j, D[i][j]); add_edge(i, j, 1); } } } rep(i, K, K + C) add_edge(s, i, 1); rep(i, 0, K) add_edge(i, t, M); return max_flow(s, t) == C; } int main() { scanf("%d%d%d", &K, &C, &M); rep(i, 0, K + C) { rep(j, 0, K + C) { scanf("%d", &D[i][j]); if(i == j) D[i][j] = 0; else if(D[i][j] == 0) D[i][j] = inf; } } rep(k, 0, K + C) { rep(i, 0, K + C) { rep(j, 0, K + C) { MIN(D[i][j], D[i][k] + D[k][j]); } } } /* rep(i, 0, K + C) { debug(vi(D[i], D[i] + K + C)); } */ int lv = 0, rv = 100000; while(rv - lv > 1) { int m = (lv + rv) / 2; if(ok(m)) rv = m; else lv = m; } printf("%d\n", rv); return 0; }
難しくはないけどWA出すとフローパートが間違ってたと思っちゃうよね。
フローはクラスじゃなくてnamespaceで管理するのがいいね。