P3701 题解

前言

题目传送门！

更好的阅读体验？

比较简单的最大流基础建图题。

以下为了方便，我们把 byx 称作 A，把诗乃酱称作 B。

思路

首先发现，人物的唯一限制就是寿命。所以：

• 从源点向每个 A 的人连边，流量是人物的寿命。
• 从每个 B 的人向汇点连边，流量是人物的寿命。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 205;
struct Edge {int now, nxt, w;} e[N * 2 + N * N];
int head[N], _head[N], cur = 1;
void add(int u, int v, int w)
{
    e[++cur].now = v, e[cur].nxt = head[u], e[cur].w = w;
    head[u] = cur;
}
void ADD(int u, int v, int w) {add(u, v, w), add(v, u, 0);}
int s, t;
bool vis[N]; int dis[N];
bool bfs()
{
    queue <int> q;
    memset(vis, false, sizeof vis);
    q.push(s), vis[s] = true, dis[s] = 0, _head[s] = head[s];
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].now;
            if (vis[v] || !e[i].w) continue;
            vis[v] = true, dis[v] = dis[u] + 1, _head[v] = head[v];
            if (v == t) return true;
            q.push(v);
        }
    }
    return false;
}
int dfs(int u, int maxflow)
{
    if (u == t) return maxflow;
    int flow = 0;
    for (int i = _head[u]; i && flow < maxflow; i = e[i].nxt)
    {
        _head[u] = i;
        int v = e[i].now;
        if (dis[v] != dis[u] + 1 || !e[i].w) continue;
        int ww = dfs(v, min(maxflow - flow, e[i].w));
        if (ww == 0) dis[v] = -114514;
        e[i].w -= ww, e[i ^ 1].w += ww, flow += ww;
    }
    return flow;
}
int dinic()
{
    int ans = 0, flow;
    while (bfs())
        while (flow = dfs(s, 2147483647))
            ans += flow;
    return ans;
}

const bool dict[5][5] = {
    0, 1, 1, 0, 0,
    0, 0, 1, 1, 0, 
    0, 0, 0, 1, 1, 
    1, 0, 0, 0, 1, 
    1, 1, 0, 0, 0
};
int read()
{
    string s;
    cin >> s;
    if (s == "J") return 0;
    if (s == "HK") return 1;
    if (s == "W") return 2;
    if (s == "E") return 3;
    if (s == "YYY") return 4;
}
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(false);
    int n, m, cnta = 0, cntb = 0;
    cin >> n >> m;
    s = 0, t = 2 * n + 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        if (a[i] == 4) cnta++; //统计YYY的个数
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] = read();
        if (b[i] == 4) cntb++; //统计YYY的个数
    }
    for (int i = 1; i <= n; i++)
    {
        int w;
        cin >> w;
        if (a[i] == 0) w += cnta; //每一个YYY都可以给J续命
        ADD(s, i, w);
    }
    for (int i = 1; i <= n; i++)
    {
        int w;
        cin >> w;
        if (b[i] == 0) w += cntb; //每一个YYY都可以给J续命
        ADD(i + n, t, w);
    }    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dict[a[i]][b[j]])
                ADD(i, j + n, 1);
    cout << min(dinic(), m);
    return 0;
}

希望能帮助到大家！