我只能自己哭了【hdu4751】

我真的只能自己哭了。

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

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

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

期间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;}