比赛 |
20110730 |
评测结果 |
AWAWAWAAAW |
题目名称 |
线段 |
最终得分 |
60 |
用户昵称 |
PurpleShadow |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-30 09:12:41 |
显示代码纯文本
#include <cstdio>
#include <cstring>
const int N=310,M=80010;
struct edge
{
int adv,next;
bool o;
};
edge es[M];
int n,m,g[N],e;
inline void addedge(int a,int b,bool o)
{
es[++e].adv=b;
es[e].o=o;
es[e].next=g[a];
g[a]=e;
}
void init()
{
scanf("%d%d",&n,&m);
memset(g,0,sizeof(g));e=0;
int a,b,c;
while (m--)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
}
bool NoAns;
bool flag[N],color[N];
void Color(int u,bool c)
{
flag[u]=1;
color[u]=c;
int v,j;
for (j=g[u];j;j=es[j].next)
{
v=es[j].adv;
if (!flag[v]) Color(v,c^es[j].o);else
NoAns|=((c^es[j].o)!=color[v]);
}
}
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;
}