Codeforces237 E. Build String 最小费用最大流

传送门：https://codeforces.com/contest/237/problem/E

题意

给一个模式串S和n个字符串，问能不能在这n个字符串中选取字符从而组成一个S。 在t_i中取一个字符的费用为i，每个字符串最大取字符个数为$a_i$。

若能组成，则输出最小费用，否则输出-1.

思路

看到这个费用，在转化成网络流模型，这题就A了。

设点： 设每个字符为1-26，n个串的为$26+i(i\epsilon n)$。源点为0，汇点为n+26+1。

建边：

  • 源点连接每个字符add(s,i,num[i],0)，字符i的个数。
  • 每个字符连接n个字符串add(i,j+26,mp[j][i],0)，第j个字符串中字符i的个数。
  • $个字符串连接汇点，add(i+26,t,a[i],j)，第j个字符串中最大可取字符个数a[i]，费用为j。

跑一遍MCMF，判断是否满流，即maxflow=n，输出mincost，否则输出-1。

Code（62MS）

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
132
133
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

##define endl "\n"
##define pb push_back
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const int INF = 0x3f3f3f3f;
// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
const double R = 0.57721566490153286060651209;

const int maxn = 1005;      //点数

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

    Edge(int u, int v, int c, int f, int cc)
            : from(u), to(v), cap(c), flow(f), cost(cc) {}
};

struct MCMF {
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn];  //是否在队列中
    int d[maxn];    //bellmanford
    int p[maxn];    //上一条弧
    int a[maxn];    //可改进量
    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; ++i) G[i].clear();
        edges.clear();
    }

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

    bool spfa(int s, int t, int &flow, int &cost) {
        for (int i = 1; i <= n; ++i) d[i] = INF;
        memset(inq, 0, sizeof(inq));
        d[s] = 0;
        inq[s] = 1;
        p[s] = 0;
        queue<int> q;
        a[s] = INF;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int i = 0; i < int(G[u].size()); ++i) {
                Edge &e = edges[G[u][i]];
                if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                    d[e.to] = d[u] + e.cost;
                    p[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] = 1;
                    }
                }
            }
        }
        if (d[t] == INF) return false;
        flow += a[t];
        cost += d[t] * a[t];
        for (int u = t; u != s; u = edges[p[u]].from) {
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s, int t, int &cost) {
        int flow = 0;
        cost = 0;
        while (spfa(s, t, flow, cost));
        return flow;
    }
} mcmf;

int n, m, mincost;

void solve() {
    string S; cin >> S;
    cin >> n;
    map<int, int> num, mp[n + 1];
    vector<int> a(n + 1);
    for(int i = 0;i < S.length(); i++) {
        num[S[i] - 'a' + 1]++;
    }
    for(int i = 1;i <= n; i++) {
        string T;
        cin >> T >> a[i];
        for(int j = 0;j < T.length(); j++) {
            mp[i][T[j] - 'a' + 1]++;
        }
    }
    int s = 0, t = n + 26 + 1;
    mcmf.init(t);
    for(int i = 1;i <= 26; i++) {
        if(!num[i]) continue;
        mcmf.add(s, i, num[i], 0); // 源点连接每个字符，流量为S串每个字符点个数
        for(int j = 1;j <= n; j++) {
            if(!mp[j][i]) continue;
            mcmf.add(i, j + 26, mp[j][i], j); // 每个字符连接n个字符串，流量为该字符串中i的个数，费用为行标j
        }
    }
    for(int i = 1;i <= n; i++) {
        mcmf.add(i + 26, t, a[i], 0); // 每个字符串连接汇点，流量为a[i]，即最大使用次数
    }
    int maxflow = mcmf.MincostMaxflow(s, t, mincost);
    if(maxflow == S.length()) cout << mincost << endl;
    else cout << -1 << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/15/codeforces237-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！