[BZOJ4549][NOI2017] game (2-SAT)


I'm a hyperlink


If there's no x, it's a 2-SAT. you can choose two tracks. The limit is the m limit given by ta

Pay special attention to the restrictions given by ta!
If you choose A, you must choose B, which means that A is not free, because you choose ta, you must choose B, so u - > v; but B is free, and choosing B does not mean choosing A, so because of symmetry, we need to connect v '- > u', which means that the symmetry point of B must choose the symmetry point of A, otherwise, if you choose A, you must choose B, and the converse no proposition still holds
The other side is relatively simple, i,hi,j,hj. If the track on i does not allow Hi, it is not necessary to add this side, anyway, it will not violate the requirements; if the track on j does not allow hj, then we must choose the symmetry point A 'of A to avoid mistakes in choosing A

Now let's take A look at x, x, we can search. The maximum is only 8. If we assume that it is only suitable for two kinds of racing cars, then we can enumerate by force that each x map is not suitable for racing car A or B (because not suitable for racing car A is suitable for racing car BC, not suitable for racing car B is suitable for racing car AC, so there are three kinds of racing cars ABC), so each map is only suitable for two kinds of racing There's A car. In judgment, if all 2^d states have been enumerated, there is no solution to the original problem, otherwise, any solution will be output.

Method of outputting any scheme: since we have already tarjan, we will directly use the belong array of tarjan order to do it. For each group of racing cars, if belong[i] < belong[i+n], select the first group, otherwise select the second group


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=4e5;
int tot,n,d,nn,top,m,nxt[N+5],v[N+5],point[N],low[N],dfn[N],stack[N],bx[N],id,belong[N],x[N],y[N],zy[20];
bool vis[N],liu=0;
char st[50005],s1[100005][10],s2[100005][10];
int get(int x,char c)
    if (bx[x]==0) return c=='B'?x:x+n;
    if (bx[x]==1) return c=='A'?x:x+n;
    if (bx[x]==2) return c=='A'?x:x+n;
int ni(int x,char c)
    if (bx[x]==0) return c=='B'?x+n:x;
    if (bx[x]==1) return c=='A'?x+n:x;
    if (bx[x]==2) return c=='A'?x+n:x;
void addline(int x,int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}
void tarjan(int x)
    low[x]=dfn[x]=++nn; vis[x]=1; stack[++top]=x;
    for (int i=point[x];i;i=nxt[i])
      if (!dfn[v[i]])
      }else if (vis[v[i]]) low[x]=min(low[x],dfn[v[i]]);
    if (low[x]==dfn[x])
        int now=0;id++;
        while (now!=x)
bool check()
    for (int i=1;i<=n*2;i++) point[i]=low[i]=dfn[i]=0;
    for (int i=1;i<=m;i++)
        if (bx[x[i]]==s1[i][0]-'A') continue;
        if (bx[y[i]]==s2[i][0]-'A') {addline(get(x[i],s1[i][0]),ni(x[i],s1[i][0]));continue;}
        addline(get(x[i],s1[i][0]),get(y[i],s2[i][0])); //A-B
        addline(ni(y[i],s2[i][0]),ni(x[i],s1[i][0])); //B'-A'
    for (int i=1;i<=n*2;i++)
      if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;i++)
      if (belong[i]==belong[i+n]) return 0;

    for (int i=1;i<=n;i++)
      if (belong[i]<belong[i+n]) 
        if (bx[i]==0) printf("B");
        else printf("A"); 
        if (bx[i]==2) printf("B");
        else printf("C");
    return 1;
void dfs(int t)
    if (t>d){if (check()) liu=1;return;}
    for (int i=0;i<=1 && !liu;i++) bx[zy[t]]=i,dfs(t+1);
int main()
    for (int i=1;i<=n;i++)
      if (st[i]=='x') zy[++d]=i;
      else bx[i]=st[i]-'a';
    for (int i=1;i<=m;i++) scanf("%d%s%d%s",&x[i],s1[i],&y[i],s2[i]);
    if (!liu) printf("-1");

Posted on Mon, 04 May 2020 08:41:39 -0700 by drag0n