还有半个月不到的时间暑假集训就开始了，这点时间里我准备复习一下网络流，毕竟已经好久没写了……其实也没有写多少
题意
网络流裸题，题目写的超级烦，简单说就是发电站供电，有很多发电站，用户和线路，问你所有发电站最多同时给用户供多少电。
思路
基础网络流建边，加一个超级源点和超级汇点即可。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 210;
const int inf = 0x3f3f3f3f;
int n, m, st, en, np, nc;
int flow[maxn][maxn], dis[maxn], que[8010], cur[maxn];
bool bfs()
{
memset(dis, -1, sizeof dis);
que[0] = st;
dis[st] = 0;
int l = 0, r = 1, u;
while (l < r) {
u = que[l++];
for (int i = 0; i < n + 2; i++)
if (flow[u][i] && dis[i] == -1) {
dis[i] = dis[u] + 1;
que[r++] = i;
}
}
return dis[en] > 0;
}
int dfs(int u, int low)
{
int cur_flow;
if (u == en)
return low;
for (int& i = cur[u]; i < n+2; i++) {
if (flow[u][i] > 0 && dis[i] == dis[u] + 1
&& (cur_flow = dfs(i, min(low, flow[u][i])))) {
flow[u][i] -= cur_flow;
flow[i][u] += cur_flow;
return cur_flow;
}
}
return 0;
}
inline void init()
{
memset(flow, 0, sizeof flow);
}
int dinic(int s, int e)
{
st = s, en = e;
int ans = 0, cur_flow;
while (bfs()) {
memset(cur, 0, sizeof cur);
while ((cur_flow = dfs(st, inf)))
ans += cur_flow;
//printf("%d\n", ans);
}
return ans;
}
int main()
{
int u, v, w;
while (scanf("%d %d %d %d", &n, &np, &nc, &m) != EOF) {
init();
while (m--) {
scanf(" (%d,%d)%d", &u, &v, &w);
flow[u][v] = w;
}
while (np--) {
scanf(" (%d)%d", &u, &w);
flow[n][u] = w;
}
while (nc--) {
scanf(" (%d)%d", &u, &w);
flow[u][n + 1] = w;
}
printf("%d\n", dinic(n, n + 1));
}
return 0;
}