Problem4.30 排列(permutation)

4.30 排列(permutation)

Description

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

Hint

n\leq500,m\leq1000,|x_i|\leq1000,保证存在至少一种排列

Solution

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

Code

#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;
}

Categories: Problem Tags: , ,

Comments

No Comments Yet. Be the first?

Post a comment