HDU6611-K subsequence(dij费用流)

题目链接:HDU6611-K subsequence

题意:

一个长度为n的序列,要求从中挑k个不下降子序列出来(每个元素只能用一次),收益为这k个不下降子序列的和,问最大收益。

题解:

费用流。

我们先建一个源点s,然后把s拆为入点s0和出点s1,然后s0向s1连容量为k,费用为0的边。

然后对于每个数ai,拆为入点ai0和出点ai1,由ai0向ai1连容量为1,费用为-ai的边。

然后s1向每个ai0连容量为1,费用为0的边,每个ai1向t连容量为1,费用为0的边。

最后对于每对i<j,a[j]>=a[i],由ai1向aj0连容量为1,费用为0的边。

最后对答案取反即可。

参考代码:

//by BigSheep 873ms
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4005;
const int inf = 0x3f3f3f3f;
int T, n, k;
int a[MAXN];
struct Edge
{
    int v, w, c, rev;
    //w流量 c费用
    Edge(int v, int w, int c, int rev) : v(v), w(w), c(c), rev(rev){};
};
vector<Edge> edge[MAXN];
void addedge(int u, int v, int w, int c)
{
    edge[u].push_back({Edge(v, w, c, edge[v].size())});
    edge[v].push_back({Edge(u, 0, -c, edge[u].size() - 1)});
}
int flow, ans; //记录最大流和最小费用
int h[MAXN], dis[MAXN];
int pre_v[MAXN], pre_id[MAXN];
struct node
{
    int u, d;
    node(int u, int d) : u(u), d(d) {}
    bool operator<(const node &a) const { return d > a.d; }
};
void MinCostFlow(int st, int ed, int Flow)
{
    memset(h, 0, sizeof(h));
    while (Flow > 0)
    {
        priority_queue<node> q;
        while (!q.empty())
            q.pop();
        for (int i = 0; i <= n * 2 + 2; i++) //总点数
            dis[i] = inf;
        dis[st] = 0;
        q.push({st, 0});
        while (!q.empty())
        {
            int u = q.top().u;
            int di = q.top().d;
            q.pop();
            if (di > dis[u])
                continue;
            for (int i = 0; i < edge[u].size(); i++)
            {
                int v = edge[u][i].v, w = edge[u][i].w, c = edge[u][i].c;
                if (w > 0 && dis[v] > dis[u] + c + h[u] - h[v])
                {
                    dis[v] = dis[u] + c + h[u] - h[v];
                    pre_v[v] = u;
                    pre_id[v] = i;
                    q.push({v, dis[v]});
                }
            }
        }
        if (dis[ed] == inf)
            break;
        for (int i = 0; i <= n * 2 + 2; i++) //总点数
            h[i] += dis[i];
        int minflow = Flow;
        for (int i = ed; i != st; i = pre_v[i])
            minflow = min(minflow, edge[pre_v[i]][pre_id[i]].w);
        Flow -= minflow;
        flow += minflow;
        ans += minflow * h[ed];
        for (int i = ed; i != st; i = pre_v[i])
        {
            Edge &e = edge[pre_v[i]][pre_id[i]];
            e.w -= minflow;
            edge[i][e.rev].w += minflow;
        }
    }
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &k);
        for (int i = 0; i <= 2 * n + 2; i++)
            edge[i].clear();
        addedge(0, 1, k, 0);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            int pos = i * 2;
            addedge(1, pos, 1, 0);
            addedge(pos, pos ^ 1, 1, -a[i]);
            addedge(pos ^ 1, n * 2 + 2, 1, 0);
        }
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (a[j] >= a[i])
                {
                    int u = (i * 2) ^ 1, v = j * 2;
                    addedge(u, v, 1, 0);
                }
        ans = 0;
        MinCostFlow(0, n * 2 + 2, inf);
        printf("%d\n", -ans);
    }
    return 0;
}
// by function2 343ms
#include <bits/stdc++.h>
#define MAXN 2000
#define MAXK 10
#define INF ((1 << 29) - 1)
using namespace std;
namespace Flow
{
const int N = 2 * MAXN + 2;
const int M = 2 * (MAXK + 4) * MAXN;
struct Edge
{
    int u, v, res, cost, next;
    Edge(int u = 0, int v = 0, int res = 0, int cost = 0, int next = 0) : u(u), v(v), res(res), cost(cost), next(next) {}
};
Edge edge[M + 10];
int head[N + 10], pp = 1;
void adde(int u, int v, int cap, int cost)
{
    edge[++pp] = Edge(u, v, cap, cost, head[u]);
    head[u] = pp;
    edge[++pp] = Edge(v, u, 0, -cost, head[v]);
    head[v] = pp;
}
int a[N + 10], p[N + 10], s, t, d[N + 10];
bool vis[N + 10];
bool spfa()
{
    for (int i = s; i <= t; i++)
    {
        d[i] = -INF;
        vis[i] = 0;
    }
    queue<int> que;
    que.push(s);
    d[s] = 0;
    vis[s] = 1;
    a[s] = INF;
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next)
        {
            const Edge &e = edge[i];
            if (e.res)
            {
                int v = e.v;
                if (d[v] < d[u] + e.cost)
                {
                    d[v] = d[u] + e.cost;
                    a[v] = min(a[u], e.res);
                    p[v] = i;
                    if (!vis[v])
                    {
                        que.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
    }
    return d[t] != -INF;
}
int mfmc(int k)
{
    int ret = 0;
    while (k && spfa())
    {
        int cur = min(k, a[t]);
        // printf("%d %d\n", a[t], d[t]);
        ret += d[t] * cur;
        for (int u, v = t; v != s; v = u)
        {
            int i = p[v];
            u = edge[i].u;
            edge[i].res -= cur;
            edge[i ^ 1].res += cur;
        }
        k -= cur;
    }
    return ret;
}
void clear()
{
    pp = 1;
    for (int i = s; i <= t; i++)
        head[i] = 0;
}
}; // namespace Flow
int a[MAXN + 10], num[MAXN + 10];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, k;
        scanf("%d%d", &n, &k);

        using Flow::s;
        using Flow::t;
        s = 0;
        t = 2 * n + 1;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", a + i);
            Flow::adde(s, i, 1, 0);
            Flow::adde(i, i + n, 1, a[i]);
            Flow::adde(i, i + n, INF, 0);
            Flow::adde(i + n, t, 1, 0);
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1, cur = INF, cnt = 0; j <= n; j++)
            {
                if (a[i] <= a[j] && a[j] < cur)
                {
                    cur = a[j];
                    cnt++;
                    Flow::adde(i + n, j, 1, 0);
                }
            }
        }
        printf("%d\n", Flow::mfmc(k));
        Flow::clear();
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。