NOI2018模拟赛(四十二)

n个数,求一个排列,使其最大字段和最大。有m个条件形如x_i必须在x_j之前。

网络流,拆点 x_{i1},x_{i2},连边S\rightarrow x_{i1}\rightarrow x_{i2}\rightarrow T

割三条边分别表示与最大子段的位置关系。限制条件连边 x_{i1}\rightarrow x_{j1},x_{i2}\rightarrow x_{j2},容量 \infty

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

const int MaxN = 1033;
const int MaxM = 50000;
const int inf = 100000000;
int n, m, cnte, sum, s, t;
int dis[MaxN], fir[MaxN], cur[MaxN];
queue<int> que;
struct edge {
    int to, nxt, cap;
    edge() {}
    edge(int a, int b, int c) {
        to = a, nxt = b, cap = c;
    }
} e[MaxM];
void addedge(int u, int v, int cap) {
    e[++cnte] = edge(v, fir[u], cap), fir[u] = cnte;
    e[++cnte] = edge(u, fir[v], 0), fir[v] = cnte;
}

bool bfs() {
    for (int i = 1; i <= t; i++)
        dis[i] = -1, cur[i] = fir[i];
    que.push(s);
    dis[s] = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = fir[u]; i; i = e[i].nxt)
            if (dis[e[i].to] < 0 && e[i].cap) {
                dis[e[i].to] = dis[u] + 1;
                que.push(e[i].to);
            }
    }
    return dis[t] != -1;
}
int dfs(int u, int f) {
    if (u == t) return f;
    for (int &i = cur[u]; i; i = e[i].nxt)
        if (dis[e[i].to] > dis[u] && e[i].cap) {
            int d = dfs(e[i].to, min(f, e[i].cap));
            if (d) {
                e[i].cap -= d, e[i ^ 1].cap += d;
                return d;
            }
        }
    return 0;
}
int mincut() {
    int res = 0;
    while (bfs()) {
        int d = 0;
        while (d = dfs(s, inf)) {
            res += d;
        }
    }
    return res;
}

int main() {
    cnte = 1;
    n = read(), m = read();
    s = n * 2 + 1, t = s + 1;
    for (int i = 1; i <= n; i++) {
        int x = read();
        if (x <= 0) {
            addedge(s, i * 2 - 1, 0);
            addedge(i * 2 - 1, i * 2, -x);
            addedge(i * 2, t, 0);
        }
        else {
            sum += x;
            addedge(s, i * 2 - 1, x);
            addedge(i * 2 - 1, i * 2, 0);
            addedge(i * 2, t, x);
        }
    }
    for (int i = 1; i <= m; i++) {
        int a = read(), b = read();
        addedge(a * 2 - 1, b * 2 - 1, inf);
        addedge(a * 2, b * 2, inf);
    }
    printf("%d\n", sum - mincut());
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注