还有半个月不到的时间暑假集训就开始了,这点时间里我准备复习一下网络流,毕竟已经好久没写了……其实也没有写多少

传送门

题意
网络流裸题,题目写的超级烦,简单说就是发电站供电,有很多发电站,用户和线路,问你所有发电站最多同时给用户供多少电。

思路
基础网络流建边,加一个超级源点和超级汇点即可。

#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;
}