POJ 1459 最大流 第二题

http://poj.org/problem?id=1459

也是网络流的基础，只是虚拟出一个源点和终点，对应的生产值和消费值就加到与源点和终点的边上，然后做一次bfs就好了。

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <algorithm>

 #define INF 999999999

 //#define OPEN_FILE

 using namespace std;

 const int MAXN = ;

 int cap[MAXN][MAXN], flow[MAXN][MAXN], p[MAXN], c[MAXN], f[MAXN];

 int n, ans;

 void get_cap(char s[])

 {

     int i, u, v, w;

     u = ;

     for (i = ; s[i] != ','; i++){

         u = u *  + (s[i] - '');

     }

     v = ;

     for (++i; s[i] != ')'; i++){

         v = v *  + (s[i] - '');

     }

     int len = strlen(s);

     w = ;

     for (++i; i < len; i++){

         w = w *  + (s[i] - '');

     }

     cap[u][v] = w;

 }

 void get_pc(char s[], int* t, int o)

 {

     int i, u, w;

     u = ;

     for (i = ; s[i] != ')'; i++){

         u = u *  + (s[i] - '');

     }

     int len = strlen(s);

     w = ;

     for (++i; i < len; i++){

         w = w *  + (s[i] - '');

     }

     if (o){

         cap[n][u] = w;

     }

     else{

         cap[u][n + ] = w;

     }

 }

 void ek_bfs(){

     queue<int> d;

     int s, t, u, v;

     int a[MAXN];

     s = n;

     t = n + ;

     ans = ;

     while (){

         memset(a, , sizeof(a));

         a[s] = INF;

         d.push(s);

         while (!d.empty()){

             u = d.front();

             d.pop();

             for (v = ; v <= n + ; v++){

                 if (a[v] || cap[u][v] <= flow[u][v]) continue;

                 f[v] = u;

                 d.push(v);

                 a[v] = min(a[u] , cap[u][v] - flow[u][v]);

             }

         }

         if (a[t] == ) break;

         for (u = t; u != s; u = f[u]){

             flow[f[u]][u] += a[t];

             flow[u][f[u]] -= a[t];

         }

         ans += a[t];

     }

 }

 int main()

 {

 #ifdef OPEN_FILE

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int m, np, nc, i, j;

     char s[];

     while (~scanf("%d%d%d%d", &n, &np, &nc, &m)){

         memset(cap, , sizeof(cap));

         memset(flow, , sizeof(flow));

         memset(p, , sizeof(p));

         memset(c, , sizeof(c));

         for (i = ; i <= m; i++){

             scanf("%s", s);

             get_cap(s);

         }

         for (i = ; i <= np; i++){

             scanf("%s", s);

             get_pc(s, p, );

         }

         for (i = ; i <= nc; i++){

             scanf("%s", s);

             get_pc(s, c, );

         }

         ek_bfs();

         printf("%d\n", ans);

     }

 }