前言
比较简单的最大流基础建图题。
以下为了方便,我们把 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;
}
希望能帮助到大家!
标签:head,return,int,题解,P3701,flow,vis,dis From: https://www.cnblogs.com/liangbowen/p/17022736.html