记录编号 |
26980 |
评测结果 |
AAAAAAAAAA |
题目名称 |
线段 |
最终得分 |
100 |
用户昵称 |
PurpleShadow |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.008 s |
提交时间 |
2011-07-30 15:05:12 |
内存使用 |
0.44 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
const int N=310;
int n,m;
bool g[N][N],exist[N][N];
void init()
{
scanf("%d%d",&n,&m);
memset(exist,0,sizeof(exist));
int a,b,c;
while (m--)
{
scanf("%d%d%d",&a,&b,&c);
exist[a][b]=exist[b][a]=1;
g[a][b]=g[b][a]=c;
}
}
bool NoAns;
bool flag[N],color[N];
void Color(int u,bool c)
{
flag[u]=1;
color[u]=c;
int j;
for (j=1;j<=n;++j)
if (exist[u][j])
{
if (!flag[j]) Color(j,c^g[u][j]);else
NoAns|=((c^g[u][j])!=color[j]);
}
}
bool Ans,Determined;
void slove()
{
memset(flag,0,sizeof(flag));
NoAns=0;
Color(1,0);
Determined=flag[n];
Ans=color[1]^color[n];
for (int i=1;i<=n;++i)
if (!flag[i]) Color(i,0);
if (NoAns) printf("No Answer\n");else
if (!Determined) printf("2\n");else
printf("%d\n",Ans);
}
int main()
{
freopen("line.in","r",stdin);
freopen("line.out","w",stdout);
int t;
scanf("%d",&t);
while (t--)
{
init();
slove();
}
return 0;
}