首页 > 代码库 > HDOJ3549-Flow Problem(最大流)
HDOJ3549-Flow Problem(最大流)
Problem Description
Input
The first line of input contains an integer T, denoting the number of test cases.For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
Output
For each test cases, you should output the maximum flow from source 1 to sink N.
Sample Input
23 21 2 12 3 13 31 2 12 3 11 3 1
Sample Output
Case 1: 1Case 2: 2
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define CLR(x , v) memset(x , v , sizeof(x)) 5 6 static const int OO = 0x3fffffff; 7 8 static const int MAXN = 1e3 + 10; 9 10 int n , m;11 int cap[MAXN][MAXN];12 int flow[MAXN][MAXN];13 int add[MAXN];14 queue<int> q;15 int pre[MAXN];16 int main()17 {18 int t;19 scanf("%d" , &t);20 for(int c = 1 ; c <= t ; ++c)21 {22 int ans = 0;23 CLR(cap , 0);24 CLR(flow , 0);25 CLR(pre , 0);26 while(!q.empty())27 q.pop();28 scanf("%d%d" , &n , &m);29 for(int i = 1 ; i <= m ; ++i)30 {31 int a , b , c;32 scanf("%d%d%d" , &a , &b , &c);33 cap[a][b] += c;34 }35 36 for(;;)37 {38 CLR(add , 0);39 add[1] = OO;40 q.push(1);41 while(!q.empty())42 {43 int u = q.front();44 q.pop();45 for(int i = 1 ; i <= n ; ++i)46 {47 if(!add[i] && cap[u][i] > flow[u][i])48 {49 pre[i] = u;50 q.push(i);51 add[i] = min(add[u] , cap[u][i] - flow[u][i]);52 }53 }54 }55 56 if(!add[n])57 break;58 59 for(int i = n ; i != 1 ; i = pre[i])60 {61 flow[pre[i]][i] += add[n];62 flow[i][pre[i]] -= add[n];//反向弧63 }64 65 ans += add[n];66 }67 68 printf("Case %d: %d\n" , c , ans);69 }70 }
HDOJ3549-Flow Problem(最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。