[洛谷P4617] [COCI2017-2018#5] Planinarenje

Description

\(Mirko\) 和 \(Slavko\) 喜欢一起去远足。\(Mirko\) 偏好攀登山峰，而 \(Slavko\) 偏爱山谷。因此每次他们登上一座山峰后，\(Slavko\) 会决定下次去哪个山谷玩（如果存在索道），同理每次游玩一个山谷后，\(Mirko\) 会决定下次去攀登哪座山峰（如果存在索道）。于是，不会出现连续两次游玩山峰或者连续两次游玩山谷的情况。为了享受更多乐趣，他们不会去已经去过的景点。 如果他们逛完一个景点后，发现接下来无法乘坐索道前往任何可行的景点，那么这次旅行就结束了。这时，如果最终景点是山峰，则 \(Mirko\) 获胜，否则 \(Slavko\) 获胜。 假设两个人都足够聪明，请你计算：从任意一座山峰开始旅行，最终谁会获胜？

Input

第一行为两个正整数 \(N\)、\(M\)，表示有 \(N\) 座山峰、\(N\) 个山谷和 \(M\) 条索道。 接下来 \(M\) 行，每行两个正整数 \(vi\) 、\(di\) ，表示在第 \(vi\) 座山峰和第 \(di\) 个山谷之间存在一条索道。任意一对山峰和山谷之间至多有一条索道。

Output

输出 \(N\) 行，每行一个字符串。第 \(i\) 行的字符串表示，假如旅行出发点是第 \(i\) 座山峰，那么最终谁会获胜。注意区分大小写。

Sample Input

4 5 2 2 1 2 1 1 1 3 4 2

Sample Output

Slavko Mirko Mirko Mirko

HINT

【数据规模与约定】

对于 \(30%\) 的数据，\(1 \leq N \leq 10\) 。

对于额外 \(20%\) 的数据，任意两个景点之间至多存在一条简单路径，构成一个森林。

对于 \(100%\) 的数据，\(1 \leq N, M \leq 5000, M \leq N ^2\)。

来源：\(NOI2019\) 北京队集训

---

想法

考试的时候当然没想出来，就写了个50分的暴力（树形 \(dp\) +状压 \(dp\)），结果因为数组开小了爆零 QwQ

正解 %%% \(hzk\) 大神 比较套路，考虑做个二分图的最大匹配。 从某个山峰处出发，若当前没有匹配，且找不到增广路，则 \(Mirko\) 赢。 为什么呢？因为不管走到哪个山谷点，都可以顺着当前的匹配边走到山峰，直到到某个山峰没有出路。

那么，得出结论： 从某个山峰出发，若这个山峰在某个最大匹配中未被匹配，则 \(Mirko\) 赢，否则 \(Slavko\) 赢。

怎么判断呢？ 先匈牙利算法跑出一个最大匹配，然后从每个非匹配的山峰点往前找增广路，找的过程中经过的山峰点都可能在某个最大匹配中未被匹配（可以这样理解，当前未匹配的点一次顺着当前找的过程中已经过的边匹配，这个新点就变成了此时的未匹配点）

---

代码

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int read(){ int x=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } const int N = 5005; struct node{ int v; node *nxt; }pool[N],*h[N*2]; int cnt; void addedge(int u,int v){ node *p=&pool[++cnt]; p->v=v;p->nxt=h[u];h[u]=p; } int n,m; int con[N],vis[N]; bool find(int u){ int v; for(node *p=h[u];p;p=p->nxt){ if(vis[v=p->v-n]) continue; vis[v]=1; if(!con[v] || find(con[v])){ con[v]=u; return true; } } return false; } int no[N]; void getno(int u){ int v; no[u]=1; for(node *p=h[u];p;p=p->nxt){ if(vis[v=p->v-n]) continue; vis[v]=1; getno(con[v]); } } int main() { int u,v; n=read(); m=read(); for(int i=0;i<m;i++) { u=read(); v=read()+n; addedge(u,v); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(find(i)) no[i]=0; else{ no[i]=1; memset(vis,0,sizeof(vis)); getno(i); } } for(int i=1;i<=n;i++) if(no[i]) printf("Mirko\n"); else printf("Slavko\n"); return 0; }

转载于:https://www.cnblogs.com/lindalee/p/11144239.html