您的位置: 首页  >  IT文章  >  【2-SAT】Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals) D. Innokenty and a Football League

【2-SAT】Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals) D. Innokenty and a Football League

分类: IT文章 • 2022-07-30 09:43:04

先反复地扫（不超过n次），把所有可以确定唯一取法的给确定下来。

然后对于剩下的不能确定的，跑2-SAT。输出可行解时，对于a和¬a，如果a所在的强连通分量序号在¬a之前，则取a，否则不取a。如果a和¬a在同一个强连通分量，则无解。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
struct data
{
	int x1,x2,id;
	string s1,s2;
};
data a[1010];
string s1,s2,anss[1010];
int cho[1010];
bool S[100010];
bool __cmp(const data &a,const data &b)
{
	return a.x1<b.x1;
}
int n;
vector<int>G[40010],rG[40010],vs;
bool used[40010],will[20010];
int cmp[40010];
void AddEdge(int U,int V)
{
	G[U].push_back(V);
	rG[V].push_back(U);
}
void dfs(int U)
{
    used[U]=1;
    for(int i=0;i<G[U].size();++i)
      if(!used[G[U][i]])
        dfs(G[U][i]);
    vs.push_back(U);
}
void rdfs(int U,int k)
{
    used[U]=1;
    cmp[U]=k;
    for(int i=0;i<rG[U].size();++i)
      if(!used[rG[U][i]])
        rdfs(rG[U][i],k);
}
bool cho2[20010];
int main()
{
//	freopen("d.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  {
	  	cin>>s1>>s2;
	  	a[i].s1=s1.substr(0,3);
	  	a[i].s2=s1.substr(0,2)+s2.substr(0,1);
	  	a[i].x1=(s1[0]-'A')*26*26+(s1[1]-'A')*26+s1[2]-'A';
	  	a[i].x2=(s1[0]-'A')*26*26+(s1[1]-'A')*26+s2[0]-'A';
	  	a[i].id=i;
	  }
	sort(a,a+1+n,__cmp);
	int sta;
	for(int i=1;i<=n;++i)
	  {
		if(a[i].x1!=a[i-1].x1) sta=i;
		if(a[i].x1!=a[i+1].x1 && i>sta)
		  {
		  	for(int j=sta;j<=i;++j)
		  	  {
		  	  	cho[j]=2;
		  	  	if(S[a[j].x2])
		  	  	  {
		  	  	  	puts("NO");
		  	  	  	return 0;
		  	  	  }
		  	  	S[a[j].x2]=1;
		  	  }
		  }
	  }
	while(1)
	  {
	  	bool flag=0;
	  	for(int i=1;i<=n;++i)
	  	  if(!cho[i])
	  	    {
	  	      if(S[a[i].x1] && S[a[i].x2])
	  	        {
	  	          puts("NO");
	  	          return 0;
	  	        }
	  	      else if(S[a[i].x1])
	  	        {
	  	          flag=1;
	  	          cho[i]=2;
	  	          S[a[i].x2]=1;
	  	        }
	  	      else if(S[a[i].x2])
	  	        {
	  	          flag=1;
	  	          cho[i]=1;
	  	          S[a[i].x1]=1;
	  	        }
	  	      else if(a[i].x1==a[i].x2)
	  	        {
	  	          cho[i]=1;
	  	          flag=1;
	  	          S[a[i].x1]=1;
	  	        }
	  	    }
	  	if(!flag)
	  	  break;
	  }
	for(int i=1;i<=n;++i)
	  if(!cho[i])
	    {
	      will[a[i].x1]=will[a[i].x2]=1;
	      AddEdge(a[i].x1,a[i].x2+20000);
	      AddEdge(a[i].x2,a[i].x1+20000);
	    }
	for(int i=1;i<=20000;++i) if(will[i])
      if(!used[i])
        dfs(i);
    memset(used,0,sizeof(used));
    int cnt=0;
    for(int i=vs.size()-1;i>=0;--i)
      if(!used[vs[i]])
        rdfs(vs[i],++cnt);
    for(int i=1;i<=20000;++i) if(will[i])
      if(cmp[i]==cmp[i+20000])
        {
          puts("NO");
          return 0;
        }
      else if(cmp[i]>cmp[i+20000])
        cho2[i]=1;
    for(int i=1;i<=n;++i)
      if(cho[i]==1)
        anss[a[i].id]=a[i].s1;
      else if(cho[i]==2)
        anss[a[i].id]=a[i].s2;
      else if(cho2[a[i].x1])
        anss[a[i].id]=a[i].s1;
      else
        anss[a[i].id]=a[i].s2;
    puts("YES");
    for(int i=1;i<=n;++i)
      cout<<anss[i]<<endl;
	return 0;
}

相关推荐