这是微软上周校招线上笔试的一道题，先贴出链接：http://

微软苏州研究院正在校招，有意愿在找工作的同学可以去试下哈：http://www.

[ 本帖最后由 书生等待 于 2015-1-19 17:06 编辑 ]

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Little Hi's super computer has a complex power system consisting of N power supply units(PSUs). Each PSU has two possible states: turned on or off. Recently Little Hi found the power system was not running stable sometimes. After careful examination, he locates M malfunctioning pairs of PSUs. For each pair ai and bi, there is a certain state si(on or off) that when ai and bi are both turned to state si, the super computer becomes unstable.

Little Hi wants to know if there is a way to keep his computer running stable.

输入
Input contains several test cases.

The first line contains an integer T(T <= 10), the number of test cases.

For each test case, the first line contains two integers N(N <= 10000) and M(M <= 200000).

The i-th line of the following M lines contains three integers ai(1 <= ai <= N), bi(1 <= bi <= N) and si(0 for turned on and 1 for turn off) indicating that if PSU ai and bi are both turned to state si, the computer will become unstable.

输出
For each test case output "Yes" or "No" without qoutes.


样例输入
1
5 6
1 2 0
1 2 1
1 3 0
1 3 1
2 3 0
2 3 1
样例输出
No

小弟就是抱着学习的心态玩下，
当时三个题我们三个一起看的，考试时间俩小时，一个半小时才把三个题看懂，一行代码都没写，哈哈

然后这两天也在想这个题，我现在是这样想的：

如果题目中给定的限定，也就是约束条件是任意两位ai 和bi 不能相等的话，那么问题就转化为图的着色问题，而且着色只能使用两种颜色。那就是检测由这些位构成的图中，是不是存在节点数为奇数的环。
但是现在题目给的限定是ai 和bi 不能同时为0，或者不能同时为1

题目给出的样例输入是很特殊的，也就是对于每对ai 和bi ，他都同时给出ai 和bi 不能同时为0 和1 的限制。这是不是一种提示？也就是，如果给出的一个约束条件 ai 和bi 不能同时为0，但是可以同时为1，或者ai 和bi 可以同时为1，但不能同时为0 。那么这个约束对于最后的结果，也就是 output yes 还是no 是没有影响的。

然后我就想验证这个想法。我还是想从样例输入出发。假设我们现在去掉样例输入中的第二行，那么样例输入变为：

样例输入
1
5 6
1 2 0

1 3 0
1 3 1
2 3 0
2 3 1

此时就由于存在三个bit 分别为 1 1 0，这样的可行解，也就是最后的输出应该是yes。

仅仅删去了一条约束，就从no 变成了yes，这是不是验证了我上面的想法，也就是约束必须成对出现，才能对于最后的结果产生影响。
而约束成对出现也就意味着对应的两个bit不能相等。也就转化成了上面说的图的二色着色问题。那么问题也就变成了只从约束出发，而且只考虑成对出现的约束，然后检测约束之间是否构成了节点个数为奇数的环。从而得到最后的结果。

在CSDN上找到了解答，不过我在理解阶段，贴出来大家学习下

原链接：http://blog.


C.Troublesome Power Supply
        　对于些对控制器定义了一些不能同时关，一些不能同时开..否则系统不稳定...由于控制器只有两种状态..所以是很明显的2-SAT


#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 20005
#define MAXM 800005
using namespace std;
struct node
{
       int x,y,next;
}edge[MAXM];
int _next[MAXN],En,dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex;
bool instack[MAXN];
stack<int> mystack;
void addedge(int x,int y)
{
       edge[++En].next=_next[x],_next[x]=En;
       edge[En].x=x,edge[En].y=y;
}
void InputData(int n,int m)
{
       int x,y,s,x0,x1,y0,y1;
       memset(_next,0,sizeof(_next)),En=0;
       while (m--)
       {
              scanf("%d%d%d",&x,&y,&s);
              x0=x<<1,x1=x0|1,y0=y<<1,y1=y0|1;
              if (!s)
              {
                    addedge(x0,y1),addedge(y0,x1);
              }else
              {
                    addedge(x1,y0),addedge(y1,x0);
              }
       }
       return;
}
void tarjan(int x)
{
       int y,k;
       dfn[x]=low[x]=++DfsIndex;
       instack[x]=true;
       mystack.push(x);
       for (k=_next[x];k;k=edge[k].next)
       {
               y=edge[k].y;
               if (!dfn[y])
               {
                      tarjan(y);
                      low[x]=min(low[x],low[y]);
               }else
               if (instack[y])
                      low[x]=min(low[x],dfn[y]);
       }
       if (low[x]==dfn[x])
       {
               tpnum++;
               do
               {
                     x=mystack.top();
                     mystack.pop();
                     tp[x]=tpnum;
                     instack[x]=false;
               }while (low[x]!=dfn[x]);
       }
       return;
}
bool judge(int n)
{
       int i;
       for (i=0;i<n;i++)
          if (tp[i<<1]==tp[i<<1|1]) return false;
       return true;
}
int main()
{
       int cases,n,m;  
       scanf("%d",&cases);
       while (cases--)
       {
                scanf("%d%d",&n,&m);
                InputData(n,m);
                memset(dfn,0,sizeof(dfn));
                memset(instack,false,sizeof(instack));
                while (!mystack.empty()) mystack.pop();
                DfsIndex=tpnum=0;
                for (int i=0;i<(n<<1);i++)
                   if (!dfn[i]) tarjan(i);
                if (judge(n)) puts("Yes");
                        else  puts("No");
       }
       return 0;
}

[ 本帖最后由 书生等待 于 2015-1-21 17:36 编辑 ]

当然我们我们当时第一反应就是遍历，

在堆上直接申请N个bit的空间，从0000000.....00000000,一直遍历到11111111.....1111111，然后对每一种0 1 组合检测是否电脑是否稳定，哈哈，这样都能想到，但是估计百分百超时了，

版主有何高见啊？

这也是一种从给定的约束出发的验证方式，但是比较怕前面的约束条件不相关

1  2  0
3  4  0
5  6  0
。。。

这种情况就会使得前面可能的情况很多，不过应该仍然可解的

多谢r版回答，你说的这个应该就是我在4楼和5楼想要表达的，不过我感觉直接把问题转化成这样，有点不大放心

我也在找这样的验证（验证正确或者错误），r版能否把你进行转化的思路描述一下

嗯，我也是从环的角度出发，没有发现bug例子。

后面我在CSDN找到人解出来了，我把代码贴到6楼了，r版可以看下，我还在理解问题阶段，哈哈