题目链接： http://poj.org/problem?id=1459
因为发电站有多个，所以需要一个超级源点，消费者有多个，需要一个超级汇点，这样超级源点到发电站的权值就是发电站的容量，也就是题目中的pmax，消费者到超级汇点的权值就是消费者的容量，也就是题目中的cmax。初学网络流，第一眼看到这个题还以为应该先做一遍EK算法，然后减去max(p-pmax, c-cmax)呢。。没想到这个题的难点就是建图而已。。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
int cap[][], flow[][], res[], pre[];
int start, end;
int n_node, n_power, n_consumer, n_line;
queue<int>que; int Edmonds_Karp()
{
while(!que.empty())que.pop();
int flow_sum = ;
while(true)
{
memset(res, , sizeof(res));
res[start] = INF;
que.push(start);
while(!que.empty())
{
int u = que.front();
que.pop();
for(int v = ; v < n_node+; v++)
{
if(!res[v] && cap[u][v] > flow[u][v])
{
pre[v] = u;
que.push(v);
res[v] = min(res[u], cap[u][v] - flow[u][v]);
}
}
}
if(res[end] == )break;
for(int u = end; u != start; u = pre[u])
{
flow[pre[u]][u] += res[end];
flow[u][pre[u]] -= res[end];
}
flow_sum += res[end];
}
return flow_sum;
} int main()
{
char fuck_space[];//18禁。。
while(scanf("%d %d %d %d", &n_node, &n_power, &n_consumer, &n_line) != EOF)
{
int u, v, w;
memset(cap, , sizeof(cap));
memset(flow, , sizeof(flow));
start = n_node;
end = n_node+;
for(int i = ; i < n_line; i++)
{
scanf("%s", fuck_space);
sscanf(fuck_space, "(%d,%d)%d", &u, &v, &w);
cap[u][v] += w;
}
for(int i = ; i < n_power; i++)
{
scanf("%s", fuck_space);
sscanf(fuck_space, "(%d)%d", &u, &w);
cap[start][u] += w;
}
for(int i = ; i < n_consumer; i++)
{
scanf("%s", fuck_space);
sscanf(fuck_space, "(%d)%d", &u, &w);
cap[u][end] += w;
}
printf("%d\n", Edmonds_Karp());
}
return ;
}