POJ 2112: Optimal Milking

にぶたんして最大流流す。

にぶたんの初期値を小さくしすぎて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で管理するのがいいね。