网络流 40pts WA+TLE 求助
查看原帖
网络流 40pts WA+TLE 求助
298424
Garbage_fish楼主2024/7/19 22:34

rt,实在找不到有什么地方能挂了

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10, oo = 1e9;
int n, m, s, t, ans;
int head[N], ide = 1;
struct EDGE {
    int v, next, w;
} edge[N];
void add(int u, int v, int w) {
    edge[++ide] = {v, head[u], w};
    head[u] = ide;
}
int dis[N], now[N];
bool bfs() {
    fill(dis, dis + N, oo);
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    now[s] = head[s];
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (edge[i].w <= 0 or dis[v] != oo)
                continue;
            q.push(v);
            now[v] = head[v];
            dis[v] = dis[u] + 1;
            if (v == t)
                return true;
        }
    }
    return false;
}
int dfs(int u, int last) {
    if (u == t)
        return last;
    int ret = 0;
    for (int i = now[u]; i and last; i = edge[i].next) {
        now[u] = i;
        int v = edge[i].v;
        if (edge[i].w <= 0 or dis[v] != dis[u] + 1)
            continue;
        int tmp = dfs(v, min(last, edge[i].w));
        if (!tmp)
            dis[v] = oo;
        edge[i].w -= tmp;
        edge[i ^ 1].w += tmp;
        ret += tmp;
        last -= tmp;
    }
    return ret;
}
signed main() {
    IOS;
    cin >> n >> m;
    s = 0, t = n + 1;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        if (x)
            add(s, i, 1);
        else
            add(i, t, 1);
    }
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        add(u, v, 1);
        add(v, u, 1);
    }
    while (bfs())
        ans += dfs(s, oo);
    cout << ans;
    return 0;
}
2024/7/19 22:34
加载中...