萌新妹子刚学OI 1e-10秒求助网络流!
查看原帖
萌新妹子刚学OI 1e-10秒求助网络流!
642247
快速herself变换楼主2023/2/17 17:17

呜呜,思路与第一篇题解一模一样,就连代码都改到几乎一样了,还是30分

#include<bits/stdc++.h>
#define il inline
#define re register
#define ll long long
#define ull unsigned ll
#define uint unsigned int
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define IT iterator
#define pr pair
#define pq priority_queue
#define mpr make_pair
#define int ll
const int N = 1e5 + 5, inf = 0x3f3f3f3f;
const double pi = acos(-1);
il int R () {
    re int s = 0, f = 1; re char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar(); 
    return s * f; 
}
int n, f, d, head[N], nxt[N], to[N], edge[N], tot = -1, S, T, cur[N], dis[N];
il void add_edge (int u, int v, int w) {
    nxt[++tot] = head[u], to[tot] = v, head[u] = tot, edge[tot] = w;
    return ;
}
std :: queue <int> q;
il int bfs () {
    std :: memset(dis, -1, sizeof(dis));
    dis[S] = 0, q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (dis[v] == -1 && edge[i]) q.push(v), dis[v] = dis[u] + 1; 
        }
    }
    return (dis[T] != -1);
}
il int dfs (int u, int flow) {
    if (u == T) return flow;
    int now = flow;
    for (int i = cur[u]; i != -1; i = nxt[i]) {
        cur[u] = i;
        int v = to[i];
        if (dis[v] == dis[u] + 1 && edge[i] > 0) {
            int minn = dfs(v, std :: min(now, edge[i]));
            edge[i] -= minn, edge[i ^ 1] += minn;
            now -= minn;
        }
        if (now <= 0) break;
    }
    return flow - now;
}
il int dinic () {
    int ret = 0;
    while (bfs()) {	
        for (int i = 1; i <= T; i++) cur[i] = head[i];
        ret += dfs(S, inf);
    }
    return ret;
}
signed main () {
    n = R(), f = R(), d = R();
    S = 1, T = n + f + d + n + f + d;
    std :: memset(head, -1, sizeof(head));
    for (int i = 1; i <= f; i++) {
        add_edge(S, i + 1, 1);
        add_edge(i + 1, S, 0);
    }
    for (int i = 1; i <= d; i++) {
        add_edge(1 + f + n + i, T, 1);
        add_edge(T, 1 + f + n + i, 0);
    }
    for (int i = 1; i <= n; i++) {
        add_edge(1 + f + i, 2 + f + n + d + i, 1);
        add_edge(2 + f + n + d + i, 1 + f + i, 0);
    }
    for (int i = 1; i <= n; i++) {
        int k1 = R(), k2 = R();
        for (int j = 1; j <= k1; j++) {
            int u = R();
            add_edge(1 + u, 1 + f + i, 1);
            add_edge(i + f + i, 1 + u, 0);
        }
        for (int j = 1; j <= k2; j++) {
            int v = R();
            add_edge(2 + f + n + d + i, 1 + v + f + n, 1);
            add_edge(1 + v + f + n, 2 + f + n + d + i, 0);
        }
    }    
    return !printf("%lld", dinic());
}
2023/2/17 17:17
加载中...