sh(s); while(!que.empty()) { int cur = que.front(); que.pop(); if(cur == t) break; //找到增广路径 for(int i = 1; i <= m; i++) { if(i != s && cap[cur][i] > 0 && pre[i] == -1) { pre[i] = cur; //记录前驱 flow[i] = min(cap[cur][i], flow[cur]); que.push(i); } } } if(pre[t] == -1) return -1; else return flow[t]; } int ek(int s, int t) { int inc = 0; int ans = 0; while((inc = bfs(s, t)) != -1) { int k = t; while(k != s) { cap[pre[k]][k] -= inc; cap[k][pre[k]] += inc; k = pre[k]; } ans += inc; } return ans; } int main() { int T; scanf("%d", &T); for(int cas = 1; cas <= T; cas++) { cin >> m >> n; memset(cap, 0, sizeof(cap)); for(int i = 0; i < n; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); if(u == v) continue; cap[u][v] += w; } cout << "Case " << cas << ": " << ek(1, m) << endl; } return 0; }
?
?
?
?
?
?
?
?
?
?
|