「HDU-6532」Chessboard (费用流)

发表于 | 分类于 ， ，

「HDU-6532」Chessboard
离散化+二分图行列模型，求限制条件下放置棋子的最大总价值

题意

给定一个棋盘，可以在给定的位置放棋子，第i个棋子的价值为i。并给出若干个限制条件，要求在某列右侧/某行下方的棋子总数不超过$k_i$，求满足限制条件情况下放置棋子可以获得的最大价值。

XTU教练：这不就是个费用流吗.jpg(震声）

解法

二分图的行列模型，数据范围需要离散化。第0行为源点，第0列为汇点；第$i-1$行向第$i$行连边，流量为第$i$行的限制；第$i$列向第$i-1$列连边，流量为第$i$列的限制，并将每个点所在的行向其所在的列连边，流量为1，费用为$-i$，跑费用流即可。

需要注意建图的时候只离散化给定的点的行和列的点作为网络上的点，对于每一个限制条件lower_bound找到第一个大于等于它的点，并更新该点的限制，最后对于lim_R[i]和lim_C[i]建图。

其实我赛场上就嘴出解法了然后因为是嘴巴选手所以敲了1h没写出来

代码

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;

struct Edge{ int from, to, cap, flow,cost; };

struct
{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];
    int dis[maxn], path[maxn], a[maxn];

    void init(int n)
    {
        this->n = n;
        for(int i = 0; i <= n; i ++) G[i].clear();
        edges.clear();
    }

    void addEdge(int from, int to, int cap, int cost)
    {
        edges.push_back(Edge{from, to, cap, 0, cost});
        edges.push_back(Edge{to, from, 0, 0, -cost});
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool Bellman_Ford(int s, int t, int &flow, int &cost)
    {
        for(int i = 0; i <= n; i ++) dis[i] = inf;
        memset(inq, 0, sizeof inq);
        dis[s] = 0, inq[s] = true, path[s] = 0, a[s] = inf;
        queue<int> Q;
        Q.push(s);
        while(!Q.empty())
        {
            int u = Q.front(); Q.pop();
            inq[u] = false;
            for(int i = 0; i < G[u].size(); i ++)
            {
                Edge& e = edges[G[u][i]];
                if(e.cap > e.flow && dis[e.to] > dis[u] + e.cost)
                {
                    dis[e.to] = dis[u] + e.cost;
                    path[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap - e.flow);
                    if(!inq[e.to])
                    {
                        Q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        if(dis[t] == inf) return false;
        flow += a[t];
        cost += dis[t] * a[t];
        for(int u = t; u != s; u = edges[path[u]].from)
        {
            edges[path[u]].flow += a[t];
            edges[path[u] ^ 1].flow -= a[t];
        }
        return true;
    }

    int mincostMaxFlow(int s, int t)
    {
        int cost = 0, flow = 0;
        while(Bellman_Ford(s, t, flow, cost));
        return cost;
    }
}ans;

int LR[maxn], LC[maxn];
int mp[510][2];

vector<int> posR, posC;

int main()
{
    int n, m, pos, k;
    char op[5];
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &mp[i][0], &mp[i][1]);
        posR.push_back(mp[i][0]);
        posC.push_back(mp[i][1]);
    }
    posR.push_back(0);
    posC.push_back(0);
    sort(posR.begin(), posR.end());
    sort(posC.begin(), posC.end());
    posR.erase(unique(posR.begin(), posR.end()), posR.end());
    posC.erase(unique(posC.begin(), posC.end()), posC.end());
    memset(LR, 0x3f, sizeof LR);
    memset(LC, 0x3f, sizeof LC);
    scanf("%d", &m);
    for(int i = 0; i < m; i ++)
    {
        scanf("%s%d%d", op, &pos, &k);
        if(op[0] == 'R')
        {
            pos = lower_bound(posR.begin(), posR.end(), pos) - posR.begin();
            LR[pos] = min(LR[pos], k);
        }
        else if(op[0] == 'C')
        {
            pos = lower_bound(posC.begin(), posC.end(), pos) - posC.begin();
            LC[pos] = min(LC[pos], k);
        }
    }
    int S = 0, T = posR.size();
    ans.init(posR.size() + posC.size());
    for(int i = 1; i < posR.size(); i ++) ans.addEdge(i - 1, i, LR[i], 0);
    for(int i = 1; i < posC.size(); i ++) ans.addEdge(i + posR.size(), i + posR.size() - 1, LC[i], 0);
    for(int i = 0; i < n; i ++)
    {
        int x = lower_bound(posR.begin(), posR.end(), mp[i][0]) - posR.begin(),
            y = lower_bound(posC.begin(), posC.end(), mp[i][1]) - posC.begin() + posR.size();
        ans.addEdge(x, y, 1, - i - 1);
    }
    printf("%d\n", -ans.mincostMaxFlow(S, T));
    return 0;
}