「Wdoi-6」最澄澈的空与海 题解

· · 题解

题目简述

已知一个左右都有 n 个节点，一共有 m 条边的二分图，求此图是否有且仅有一种完全匹配方案。是则输出 Renko，否则输出 Merry。

题目分析

这是一道结论题，先说结论，当一个二分图有且仅有一种解时，必定有节点的入度为 1。

如何证明？ 因为只要入度为 2 的情况被证明了，入度大于 2 的情况就都可以通过删边转换过来，所以 考虑反证法，证明当所有节点的入度为 2 时，只有以下两种情况：

  1. 有解时，解的数量一定大于 1
  2. 无解时...就是无解（废话）

无解的情况很好说明，只要找到一个例子就行了，剩下的就是有解的情况。

因为有解，所以我们可以先建一个节点一一对应的二分图，然后在这张图上加边，试图将其变成所有节点入度为 2 的二分图，起始状态如下图。

我们只考虑一边的节点，因为两边是对称的。

左边的每个节点都已经有了一个右边的第一选择，也就是现在连着的节点，他们还需要一个右边的第二选择来让自己的度数变成 2。

两个不同的节点可能选相同的节点作为第二选择，我们按第二选择的不同节点数量来分类讨论。

当作为第二选择的节点的数量为 1 时，也就是所有节点的第二选择都是同一个点时...这种情况并不存在，因为如果是这样的话，被选为第二选择的那一个节点对面的节点就没有可选的第二选择了，因为那是它的第一选择，它不能再选一次同样的。

当作为第二选择的节点的数量为 2 时，我们设被选为第二选择的节点为 A 与 B。 A 节点对面的节点一定会选 B 作为第二选择。 B 节点对面的节点也一定会选 A 作为第二选择。这就形成了一个交叉，交叉一定会产生第二种匹配方法。

如下图所示，黄色的是新增的边，第二选择的 A 与 B 是节点 2 与 4。1 改选 4，3 改选 2，就有了第二种匹配方法。

同样地，当作为第二选择的节点的数量为 3 时，如下图所示，2、4、6 是第二选择节点。1、2、3、4、5、6 节点的新边产生了第二种解法。

但这只是当第二选择节点对面的所有节点的第二选择都不重复时的必然情况，如果重复了呢？

如下图所示，作为第二选择的 6 与 2 对面的节点都选了 4 作为第二选择。

熟悉的交叉又出现了，对，就是第二选择节点数为 2 时的情况，所以一定也有第二种解法。

通过以上的观察（并没有严格证明，只是助于理解），我们可以得到一个重要结论：

  1. 当第二选择节点对面的节点的第二选择不重复时，直接就能找到第二种匹配方法
  2. 有重复时，会出现之前的某种情况，然后找到第二种匹配方法。

于是乎，不管怎样添边，都会出现第二种匹配方法，所以当二分图的所有节点度数为 2 并且有解时，解的数量一定大于 1。

结论有了，该怎么用呢？需要注意的是这只是一个必要非充分条件，也就是说满足题意所说的有且仅有一个解的情况一定会出现入度为 1 的节点，但并不代表有入度为 1 的节点的二分图就一定满足题意。

幸运的是，咱们会写程序。我们可以每次找到入度为 1 的节点，也就是只有一条边的节点。然后顺着那条唯一的边找到对面的一个节点。这两个节点一定是锁死的，因为如果它俩不在一起，入度为 1 的点就没有别的选择了，二分图也就无解了。

既然它俩的关系已经确定了，那么它俩就对剩余节点的匹配就没有影响了，我们就可以将它俩连点带边全部删掉。注意，边也要删掉，以此减少某些节点的入度。

就这样一直迭代下去，如果可以全部删完，那么就是满足题意的，删不完就是说有入度都大于 2 的子问题，只有无解或者解的数量大于 1 的可能，不满足题意。

每次寻找入度为 1 的节点太耗时间了，我们可以考虑类似拓扑排序的做法，但不是将入度变为 0 的节点点入队，而是将入度变为 1 的节点入队。

code:

#include<bits/stdc++.h>
#define N 2000005
#define ll long long
using namespace std;

int t,n,m,cnt;
vector<int> to[N];
int in[N];
bool del[N];

void solve(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v; v+=n; //右边的点重新编号
        to[u].push_back(v); in[v]++;
        to[v].push_back(u); in[u]++;
    }
    queue<int> q; cnt=0;
    for(int i=1;i<=2*n;i++)
        if(in[i]==1)q.push(i); //将入度为1的点入队
    while(!q.empty()){
        int now=q.front(),buf=0; q.pop();
        if(del[now]||in[now]!=1)continue; //如果已经没删掉了，或者入度不为1了，那就跳过。已经入队的点的状态也可能被改变，因为这里是左右两边一起迭代的。
        del[now]=true; cnt++; //删掉这个点，删掉的数量加1
        while(del[to[now][buf]])buf++; //找到仅存的那一条边
        del[to[now][buf]]=true; cnt++; //顺着仅存的边找到另一个点，删掉
        for(int i=0;i<to[to[now][buf]].size();i++) //删边，没有真的删，只是减少目标节点的入度，这也是为什么要用while找仅存的边。
            if(!del[to[to[now][buf]][i]]&&(--in[to[to[now][buf]][i]])==1)
                q.push(to[to[now][buf]][i]); //如果还没被删，并且入度减少为1了就入队
    }
    if(cnt==n*2)cout<<"Renko"<<endl; //全删了
    else cout<<"Merry"<<endl;  //没全删
    for(int i=1;i<=n*2;i++)in[i]=del[i]=0,to[i].clear(); //多组数据，要初始化
}

int main(){
    cin>>t;
    while(t--)solve();
    return 0;
}