给个题目链接:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1714

显然每个人只有两种选择：C或者A/B。而且后一种只和这个人的年龄有关。

这就是一个很显然的2-SAT模型了，显然有矛盾的不能都选C，如果两个人的年龄段还一样，那就更悲剧了，也不能同时选A/B。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define pb push_back#define ll long long#define maxn 200005#define M(x) memset(x,0,sizeof(x))using namespace std;int n,m;struct TOW_SAT{ vector
            
              g[maxn]; int tp[maxn],age[maxn]; int tot,node[maxn],num; bool mark[maxn<<1|1]; inline void init(){ for(int i=(n<<1)-1;i>=0;i--) g[i].clear(); M(tp),M(age); M(mark); tot=num=0; } inline void add(int x,int y){ int Cx=x<<1,Ax=Cx+1; int Cy=y<<1,Ay=Cy+1; g[Cx].pb(Ay),g[Cy].pb(Ax); if(tp[x]==tp[y]){ g[Ax].pb(Cy); g[Ay].pb(Cx); } } bool dfs(int x){ if(mark[x^1]) return 0; if(mark[x]) return 1; mark[x]=1,node[++num]=x; for(int i=g[x].size()-1;i>=0;i--) if(!(dfs(g[x][i]))) return 0; return 1; } inline bool work(){ int cl=n<<1; for(int i=0;i
             
              =tot) tp[i]=1; int uu,vv; for(int i=1;i<=m;i++){ scanf("%d%d",&uu,&vv); uu--,vv--,add(uu,vv); } if(!work()) puts("No solution"); else{ for(int i=0;i