学步园

我真的只能自己哭了。

本来最近在搞图论，上一场网赛本来判桥那个就应该是我的菜，可却因为平时判桥的代码没搞，结果找模板用不好。

上一场那个学长过了。      不过前面的确是耗掉了太多罚时。

这一场我先看的那个异或+貌似线段树那个，没有思路。换。

期间xl过了两题。 ORZ。。。。

然后看1004WA了好几发，我考虑了一会就敲完了2-SAT的代码，可任何测试数据都是YES。。。

我一起渴望着自己亲手过掉题。。     也别让自己每次都这么沉默般的打酱油。

好久没这么激动的敲代码了，就像考试时终于想出一道题的思路一样。。

tmd忽然又想起自己以前出现过的类似的考试状态。     心跳加速。。

最终这题还是没能由我切掉。   果然我又悲剧般的打酱油了。。。

烦躁的心情+杂乱的环境，我也不想再呆。

N久后到现在。

我实在是无奈了。   输出match结果全为0。   无奈中的无奈后N久。

我按步调试，最后tm发现我的solve直接退出。 WOCAO！

尼玛全局变量和局部变量重了

改了之后速A了。。。。

哎，忽然又想开了。

至少我会记得这样的错误。  一开始读入的那些数据最好都设了全局变量。

感觉图论、计算几何或者数论的一部分，的确应该是我的菜。  

尽管我同时也领悟了，自己必须多加复习才能掌握。   比如让我现在再敲个spfa，也许说不定又会有点麻烦。。。  要是敲个线段树，说不定还会有大麻烦。。。

本来想速切道题炫耀一番，无奈我又该沉默了。    就这样当一个沉默者吧。  但不在沉默中死去。

附个代码：

学长们还有一个思路，  补图+二分判定。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

#define clr(x,y) memset(x,y,sizeof(x))

const int maxn = 1500;
int n,m;
vector<int> G[maxn*3];
bool mark[maxn*3];
int s[maxn*3],c;
char op[10];
int map[105][105];
int visit[105];

bool dfs(int x)
{
    if(mark[x^1]) return false;//这个一定是强连通分量果然
    if(mark[x]) return true;
    mark[x]=true;
    s[c++]=x;
    for(int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i])) return false;
    return true;
}

void init()
{
    for(int i=0;i<n*2;i++)  G[i].clear();
    memset(mark,0,sizeof(mark));
}

bool solve()
{
    for(int i = 0;i < n*2; i += 2)
    {
      if( !mark[i] && !mark[i+1] )
      {
          c = 0;
          if( !dfs(i) )
          {
              while(c>0)
                mark[s[--c]]=false;
              if(!dfs(i+1)) return false;
          }
      }
    }
    return true;
}

int main()
{
    int num;
    while(scanf("%d", &n) != EOF)
    {
       clr(map, 0);


       for(int i = 0;i < n;i++)
       {
           while(true)
           {
              scanf("%d", &num);
              if(!num) break;
              else
              {
                  num--;
                  map[i][num] = 1;
              }
           }
       }

       init();

       for(int i = 0;i < n;i++)
       {
         clr(visit, 0);
         for(int j = 0;j < n;j++)
           {
               if(i != j)
               {
                   if(map[i][j] && map[j][i])
                      visit[j] = 1;
               }
           }
         for(int j = 0;j < n;j++) if(!visit[j] && i != j)
          {
             G[i*2].push_back(j*2+1);
             G[i*2+1].push_back(j*2);
          }
       }

      if(solve())
      {
          printf("YES\n");
      }
      else printf("NO\n");

    }
    return 0;
}