洛谷P4843 清理雪道（有源汇的上下界的网络流）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1000000000
#define maxN 505
using namespace std;

int N, S, T, s, t;

int d[maxN];

struct Edge {
    int dis, nxt, to;
}e[20005];
int cnte = 1, head[maxN];

inline void add_Edge(int i, int j, int k) { 
    e[++cnte].dis = k, e[cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte; 
    e[++cnte].dis = 0, e[cnte].nxt = head[j], e[cnte].to = i, head[j] = cnte;
}

inline void Add(int u, int v, int down, int up) {
    add_Edge(u, v, up - down), d[v] += down, d[u] -= down;
}

void Build() {
    cin >> N;
    s = N + 1, t = N + 2, S = N + 3, T = N + 4;
    for(int i = 1, m; i <= N; ++i) {
        cin >> m,
        Add(i, t, 0, INF), Add(s, i, 0, INF);
        for(int j = 1, to; j <= m; ++j) {
            cin >> to, 
            Add(i, to, 1, INF);
        }
    }
    for(int i = 1; i <= t; ++i) {
        if(d[i] > 0) add_Edge(S, i, d[i]);
        else if(d[i] < 0) add_Edge(i, T, -d[i]);
    }
}
int dep[maxN];
bool bfs() {
    queue <int> Q;
    memset(dep, 0, sizeof(dep));
    dep[S] = 1, Q.push(S);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int v, i = head[u]; i; i = e[i].nxt) {
            if(!dep[v = e[i].to] && e[i].dis) {
                dep[v] = dep[u] + 1, Q.push(v);
            }
        }
    }
    return dep[T];
}
int dfs(int u, int in) {
    if(u == T) return in;
    int out = 0;
    for(int v, i = head[u]; i && in; i = e[i].nxt) {
        if(e[i].dis && dep[v = e[i].to] == dep[u] + 1) {
            int tmp = dfs(v, min(in, e[i].dis));
            e[i].dis -= tmp, e[i ^ 1].dis += tmp,
            in -= tmp, out += tmp;
        }
    }
    if(!out) dep[u] = 0;
    return out;
}
int main() {
    Build();
    while(bfs()) dfs(S, INF);
    add_Edge(t, s, INF);
    while(bfs()) dfs(S, INF);    
    cout << e[cnte].dis << ‘\n‘;
    return 0;
}