| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
注意竟然多组数据!WA一次!样例只给一组太阴险了! #include <iostream> #include <stdio.h> #include <queue> using namespace std; int ditches[250][250] = {0}; int val = 0; int N, M; void init(){ val = 0; for(int i = 0; i < 250; i++){ for(int j = 0; j < 250; j++){ ditches[i][j] = 0; } } } bool pushFlow(){ int trc[250] = {0,1,0}; queue<int> bfs; bfs.push(1); while(!bfs.empty()){ int pt = bfs.front(); bfs.pop(); for(int i = 1; i <= M; i++){ if(trc[i] == 0 && ditches[pt][i] > 0){ trc[i] = pt; if(i == M) goto done; bfs.push(i); } } } done: if(trc[M] == 0) return 0; int thisFlow = 2147483647; int dest = M; while(dest != 1){ int tempFlow = ditches[trc[dest]][dest]; if(tempFlow < thisFlow) thisFlow = tempFlow; dest = trc[dest]; } dest = M; while(dest != 1){ ditches[trc[dest]][dest] -= thisFlow; ditches[dest][trc[dest]] += thisFlow; dest = trc[dest]; } val += thisFlow; return 1; } int main() { while(scanf("%d%d", &N, &M) > 0){ for(int i = 0; i < N; i++){ int from, to, flow; scanf("%d%d%d", &from, &to, &flow); ditches[from][to] += flow; } while(pushFlow()){;} printf("%d\n", val); init(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator