1426E.Rock, Paper, Scissors
Description
Analysis
题意概述
两个玩家共玩
n
n
n 场
(
1
≤
n
≤
1
0
9
)
(1\le n\le10^9)
(1≤n≤109)石头剪刀布，给出其分别出石头、剪刀、布的次数
求玩家
1
1
1 最少或最多可能的获胜次数
分析（基于
M
C
M
F
MCMF
MCMF 的解法）
（看到
f
l
o
w
flow
flow 的标签就直接上网络流了，简单琢磨了一下建图方式，没有标签以作者目前的实力可能无法
a
c
ac
ac ）
最小费用最大流
a
n
d
and
and 最大费用最大流（分别对应最少获胜次数和最多获胜次数）
建图分析
源点
S
→
0
S\to0
S→0，汇点
T
→
7
T\to7
T→7玩家
1
1
1：
a
1
,
a
2
,
a
3
→
a_1,a_2,a_3\to
a1,a2,a3→ 剪刀、石头、布
→
\to
→ 节点
1
,
2
,
3
1,2,3
1,2,3玩家
2
2
2：
b
1
,
b
2
,
b
3
→
b_1,b_2,b_3\to
b1,b2,b3→ 剪刀、石头、布
→
\to
→ 节点
4
,
5
,
6
4,5,6
4,5,6
S
S
S 向玩家
1
1
1 的对应节点连接一条容量为
a
i
a_i
ai，费用为
0
0
0 的边
玩家
2
2
2 的对应节点向
T
T
T 连接一条容量为
b
i
b_i
bi，费用为
0
0
0 的边
玩家
1
1
1 的对应节点向玩家
2
2
2 的对应节点连接一条容量为
∞
\infin
∞ 的边，费用：平局/负：
0
0
0，胜利：
1
1
1
原网络的每一个可行流，对应一场合法的游戏，总费用即为玩家
1
1
1 的胜利次数
以此，求最小费用最大流
a
n
d
and
and 最大费用最大流即可
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr const int N = 10, M = 40, inf = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], f[M], idx;
int dist[N], d[N], pre[N], q[N], hh, tt;
bool st[N];
int n, S, T, x, flow, cost;
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa()
{
memset(d, 0, sizeof d);
memset(dist, 0x3f, sizeof dist);
hh = 0, tt = 1;
q[0] = S, d[S] = inf, dist[S] = 0;
while(hh != tt){
int u = q[hh++];
if(hh == N) hh = 0;
st[u] = 0;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(f[i] && dist[j] > dist[u] + w[i]){
dist[j] = dist[u] + w[i];
d[j] = min(d[u], f[i]);
pre[j] = i;
if(!st[j]){
st[j] = 1;
q[tt++] = j;
if(tt == N) tt = 0;
}
}
}
}
return d[T] > 0;
}
void EK(int& flow, int& cost)
{
flow = cost = 0;
while(spfa())
{
flow += d[T], cost += dist[T] * d[T];
for(int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
memset(h, -1, sizeof h);
S = 0, T = 7;
for(int i = 1; i <= 3; i++)
{
cin >> x;
add(S, i, x, 0);
add(i, i + 3, inf, 0);
}
for(int i = 1; i <= 3; i++)
{
cin >> x;
add(i + 3, T, x, 0);
}
add(1, 5, inf, 1);
add(1, 6, inf, 0);
add(2, 4, inf, 0);
add(2, 6, inf, 1);
add(3, 4, inf, 1);
add(3, 5, inf, 0);
EK(flow, cost);
cout << cost << " ";
for(int i = 0; i < idx; i += 2)
{
f[i] += f[i ^ 1], f[i ^ 1] = 0;
w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
}
EK(flow, cost);
cout << -cost << '\n';
return 0;
}
