SP10589 KING - King 题解

FFTotoro · 2023-07-05 21:19:29 · 题解

2-SAT 算法板子题，和满汉全席特别像。

为了便于表示出推导关系，对于每个人 i 拆成两个点：点 i 和点 i+n。

接着考虑如何建边：对于每个公民的两个要求，因为至少要求满足一个，所以如果其中一个不满足可以推出另一个条件一定满足。

所以，对于某个公民的两个要求 1,2，要求内容分别为 c_1\ p_1 和 c_2\ p_2（其中 c 为字符，表示公民是否同意 p 进入第二轮选拔），令 u=p_1+[c_1=\texttt{U}]\cdot n，v=p_2+[c_2\ne \texttt{U}]\cdot n，则从 u 向 v 连边。注意，两个要求可以调换一下顺序再建边。这里 [] 表示艾弗森括号。

最后只要跑一遍 tarjan 缩点算法，对于每个人 i，判断 i 和 i+n 是否在同一个强连通分量内。如果存在 i 答案为是就表示两个矛盾的条件都可以互相推导出来，一定无解；否则一定有解。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; while(cin>>n&&n){
    int o=0,r=0;
    vector<int> d(n<<1),l(n<<1),c(n<<1);
    vector<vector<int> > g(n<<1);
    stack<int> s;
    bool f=true;
    for(int i=0;i<n;i++){
      char c1,c2; int p1,p2; cin>>c1>>p1>>c2>>p2;
      g[p1+n*(c1=='U')].emplace_back(p2+n*(c2!='U'));
      g[p2+n*(c2=='U')].emplace_back(p1+n*(c1!='U'));
    } // 建边部分
    function<void(int)> tarjan=[&](int u){
      d[u]=l[u]=++o,s.emplace(u);
      for(int i:g[u])
        if(!d[i])tarjan(i),l[u]=min(l[u],l[i]);
        else if(!c[i])l[u]=min(l[u],d[i]);
      if(d[u]==l[u]){
        r++; while(s.top()!=u)
          c[s.top()]=r,s.pop();
        c[u]=r,s.pop();
      }
    }; // 缩点 tarjan 部分
    for(int i=0;i<n<<1;i++)
      if(!d[i])tarjan(i);
    for(int i=0;i<n;i++)
      f&=c[i]!=c[i+n]; // 判断是否有解
    cout<<(f?'Y':'N')<<endl;
  }
  return 0;
}