[NOI2017]游戏 2-sat

～～～题面～～～

题解：

　　首先观察到，如果没有x的话，这就是一个2-sat问题。

　　建图方式：对于限制d1 c1 d2 c2,其中d1, d2分别代表比赛编号，c1, c2代表出场的赛车。

　　1，如果d1不能选c1,那么该限制是不会起到作用的，所以不连边。

　　2，否则如果d2不能选c2，那么意味这d1-c1不能被选，所以连d1-c1 --- > d1-c2的边，表示必须取d1-c2。

　　3，否则都可以选，所以连d1-c1 ---> d2-c2 , d1-c2 ---> d2-c1.

　　跑tarjan求强连通分量即可。

　　那么有x应该怎么做？

　　观察到对于一组数据，x最多有8场，所以3^8枚举每场x的比赛是abc中的哪种（不选哪辆车），然后在跑2-sat即可。

　　这里输出方案可以不用反向建边+拓扑排序，因为栈是后进先出，所以先出栈的点刚好是反向建边+拓扑排序后先遇到的点，因此只需要记录每个点所在的联通块编号，然后对于每场比赛选择联通块编号小的方案输出即可。

　　题目数据极水，A了也不一定是正确代码，请特别注意检查代码正确性。（如果你发现我有哪里错了也可以告诉我QAQ)

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 300100

 #define ac 1000000

 int n, d, timer, all, m;

 int s[AC], dfn[AC], low[ac], belong[ac], d1[AC], c1[AC], d2[AC], c2[AC];

 int sta[AC], top;

 int Head[AC], Next[ac], date[ac], tot;

 char ss[AC];

 bool flag, z[AC];

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x =  * x + c - '', c = getchar();

     return x;

 }

 inline void upmin(int &a, int b)

 {

     if(b < a) a = b;

 }

 inline void add(int f, int w)

 {

     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot;

     //printf("%d ---> %d\n", f, w);

 }

 void tarjan(int x)

 {

     int now;

     dfn[x] = low[x] = ++ timer, sta[++top] = x, z[x] = true;

     for(R i = Head[x]; i; i = Next[i])

     {

         now = date[i];

         if(!dfn[now])

         {

             tarjan(now);

             upmin(low[x], low[now]);

         }

         else if(z[now]) upmin(low[x], low[now]);//已经出栈的无需考虑

     }

     if(low[x] == dfn[x])

     {

         ++all;

         while()

         {

             now = sta[top--], belong[now] = all, z[now] = false;//标记出栈

             if(now == x) break;

         }

     }

 }

 void init()

 {

     tot = all = timer = ;

     memset(Head, , sizeof(Head));

     memset(dfn, , sizeof(dfn));

     memset(z, , sizeof(z));

 }

 inline int get(int x, int color)

 {

     if(s[x] == color) return ;//不合法

     if(s[x] == ) return x *  + color - ;

     else if(s[x] == ) return x *  + ((color == ) ?  : );

     else return x *  + color - ;

 }

 void build()

 {

     init();

     for(R i = ; i <= m; i ++)

     {

         int x = get(d1[i], c1[i]), y = get(d2[i], c2[i]);

         if(x)

         {

             if(y) add(x, y), add(y ^ , x ^ );

             else add(x, x ^ );

         }

     }

     int b = n *  + ;

     for(R i = ; i <= b; i ++)

         if(!dfn[i]) tarjan(i);

     for(R i = ; i <= b; i += )//error !!!到b

         if(belong[i] == belong[i ^ ]) return ;

     for(R i = ; i <= n; i ++)

     {

         int x = i * ;

         if(s[i] == ) putchar(belong[x] < belong[x ^ ] ? 'B' : 'C');

         else if(s[i] == ) putchar(belong[x] < belong[x ^ ] ? 'A' : 'C');

         else putchar(belong[x] < belong[x ^ ] ? 'A' : 'B');

     }

     flag = true;

 }

 void pre()

 {

     char ch;

     n = read(), d = read();

     scanf("%s", ss + );

     for(R i = ; i <= n; i ++)

         if(ss[i] != 'x') s[i] = ss[i] - 'a' + ;

     m = read();

     for(R i = ; i <= m; i ++)

     {

         d1[i] = read(), cin >> ch, c1[i] = ch - 'A' + ;

         d2[i] = read(), cin >> ch, c2[i] = ch - 'A' + ;

     }

 }

 void dfs(int x)

 {

     if(flag) return ;

     if(x > n)

     {

         build();

         return ;

     }

     if(!s[x])

     {

         s[x] = , dfs(x + );

         s[x] = , dfs(x + );

         s[x] = , dfs(x + );

         s[x] = ;

     }

     else dfs(x + );

 }

 int main()

 {

     freopen("in.in","r",stdin);

     pre();

     dfs();

     if(!flag) printf("-1");

     fclose(stdin);

     return ;

 }

巴特西

[NOI2017]游戏 2-sat

最新文章

热门文章