Description

有 n 个数 x 1 ~x n 。你需要找出它们的一个排列,满足 m 个条件,每个条件形 如 x a 必须在 x b 之前。在此基础上,你要最大化这个排列的最大子段和

Hint

,保证存在至少一种排列

Solution

考虑最小割，把问题转化成删掉一些点 首先，对于最后的的答案,一定形如“不选->选->不选”这样的三段。 那么，将每个点拆成 S->i1->i2->T,割不同的三条边分别表示在不同的三段中。 对于每个点，如果它的值大于0，那么从S向i1，i2向T分别连容量为权值的边； 否则从i1向i2连容量为权值的相反数的边 每个限制(a,b)，我们如果将(a1,b1), (a2,b2)连上容量为正无穷的边，就能保证a和b一定在相同的割集中，也就满足了这个限制。 答案就是正的权值和-最小割

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2000 + 10, Maxm = 8000 + 10, S = 2002, T = 2003, inf = 0x3f3f3f3f;

int N, M;
int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];

inline void add_edge (int x, int y, int z)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e++] = z;
}

inline void Link (int x, int y, int z)
{
    add_edge (x, y, z);
    add_edge (y, x, 0);
}

namespace Flow
{
    int Dis[Maxn];

    inline int bfs ()
    {
        queue <int> Q;
        Q.push(S);
        memset(Dis, -1, sizeof Dis);
        Dis[S] = 0;
        while (!Q.empty())
        {
            int x = Q.front(); Q.pop();
            for (int i = Begin[x]; ~i; i = Next[i])
            {
                int y = To[i];
                if (W[i] <= 0 || Dis[y] != -1) continue;
                Dis[y] = Dis[x] + 1;
                Q.push(y);
            }
        }
        return Dis[T] != -1;
    }

    inline int find (int x, int now)
    {
        if (x == T) return now;
        for (int i = Begin[x]; ~i; i = Next[i])
        {
            int y = To[i], sum;
            if (W[i] > 0 && Dis[y] == Dis[x] + 1 && (sum = find(y, min(now, W[i]))))
            {
                W[i] -= sum;
                W[i ^ 1] += sum;
                return sum;
            }
        }
        return 0;
    }

    inline int work ()
    {
        int ans = 0;
        while (bfs())
        {
            int sum = 0;
            while (sum = find(S, inf)) ans += sum;
        }
        return ans;
    }
}

int main()
{
    freopen("permutation.in", "r", stdin);
    freopen("permutation.out", "w", stdout);
    memset(Begin, -1, sizeof Begin);
    scanf("%d%d", &N, &M);
    int sum = 0;
    for (int i = 1; i <= N; ++i)
    {
        int x;
        scanf("%d", &x);
        if (x > 0)
        {
            sum += x;
            Link(S, i, x);
            Link(i + N, T, x);
        }
        else 
        {
            Link(i, i + N, -x);
        }
    }
    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        Link(x, y, inf);
        Link(x + N, y + N, inf);
    }
    printf("%d\n", sum - Flow :: work());
    return 0;
}