Power Network

水题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 200;
const int max_m = 1e5;
struct edge{
    int to, cap, rev, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}
int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n, -1);
    queue<int> que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}

int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}

int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}
int n, np, nc, m;
int main() {
    while (scanf("%d %d %d %d", &n, &np, &nc, &m) != EOF) {
        fill(head, head + n + 10, 0);cnt = 1;
        int start = n + 1;int ed = start + 1;
        for (int i = 1, u, v, c;i <= m;++i) {
            scanf(" (%d,%d)%d", &u, &v, &c);
            add(++u, ++v, c);
        }for (int i = 1, u, z;i <= np;++i) {
            scanf(" (%d)%d", &u, &z);
            add(start, ++u, z);
        }for (int i = 1, u, z;i <= nc;++i) {
            scanf(" (%d)%d", &u, &z);
            add(++u, ed, z);
        }printf("%d\n", dinic(start, ed));
    }
}