“蔚来杯“2022牛客暑期多校训练营10 EF题解
E-Reviewer Assignment
题目大意：
有n个审稿人和m篇论文，要求给每个审稿人安排一篇论文，给出每个审稿人能够审的论文集合。
定义f(i)为至少被i个审稿人审核的论文数量，要求f(1),f(2),...,f(n)组成的字典序最大。输出每个审稿人都审核哪篇论文。
数据范围：1<= n,m <=400
思路：
首先注意到题目中的点数是比较少的，所以用邻接矩阵存图跑最大流的话可以很方便的知道流量的流向。
那么可以这样建图：
源点向每个审稿人连一条容量为1的边，每个审稿人向能够审的论文连一条容量为1的边，每篇论文向汇点连一条容量为x的边，x从1取到n，一共跑n次最大流，相当于每次在上一次的基础上找增广路，不会影响到上一次的f值，这样就可以让f(1),f(2),...,f(n)的字典序最大了。
如何得到流向：例如审稿人x和论文y，如果边xy的容量为0，yx的容量不为0，说明审稿人x审的就是论文y。
F-Shannon Switching Game?
题目大意：
给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，Cut Player先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。
思路：
当时想到了一个点到t点如果有两种路径的话，那么这个点一定可以到达。不过当时直接跑dfs找点超时了。
题解给的做法是维护一个点的集合。集合中初始有一个点t。如果一个没有在集合中的点有两条以上的边连向集合里的点，那么这个点肯定也可以归到集合中。不断重复这个过程，最后判断s点是否在集合中即可。
至于为什么要从t开始扩展集合而不是从s开始扩展，下面这组数据可以进行说明：
1
1 4 1 3
1 3
1 2
2 3
2 3
显然结果是Join Player，但是从s开始扩展的话结果是Cut Player。
AC代码：
#include <bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e2 + 5;
using namespace std;
struct edge
{
int to, next;
} e[2 * N * N];
int head[N], ecnt;
void add(int u, int v) { e[++ecnt].next = head[u], e[ecnt].to = v, head[u] = ecnt; }
void einit()
{
ecnt = 0;
for (int i = 0; i < N; i++)
head[i] = 0;
}
int d[N];
bool vis[N];
void solve()
{
int n, m, s, t, u, v;
cin >> n >> m >> s >> t;
einit();
mem(d, 0);
mem(vis, 0);
while (m--)
{
cin >> u >> v;
add(u, v);
add(v, u);
}
queue<int> q;
q.push(t);
vis[t] = 1;
while (q.size())
{
u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].next)
{
v = e[i].to;
if (vis[v]) continue;
d[v]++;
if (d[v] >= 2)
{
vis[v] = 1;
q.push(v);
}
}
}
if (d[s] >= 2)
cout << "Join Player\n";
else
cout << "Cut Player\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}