比赛 |
20110730 |
评测结果 |
AWAWAWAAAW |
题目名称 |
线段 |
最终得分 |
60 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-30 08:59:43 |
显示代码纯文本
#include <cstdio>
#include <cstring>
const int MAXN=305,MAXM=40005;
struct Node
{
int v,w;
Node *next;
Node (){}
Node (int _v,int _w,Node *_next):v(_v),w(_w),next(_next){}
void *operator new(size_t,void *p){return p;}
}*adj[MAXN],pool[MAXM*2],*mem;
inline void addedge(int u,int v,int w)
{
adj[u]=new (mem++)Node(v,w,adj[u]);
adj[v]=new (mem++)Node(u,w,adj[v]);
}
bool flag;
int lv[MAXN],belong[MAXN];
int tot;
void dfs(int u)
{
belong[u]=tot;
for(Node *p=adj[u];p && flag;p=p->next)
if (lv[p->v]==-1)
{
lv[p->v]=lv[u]^p->w;
dfs(p->v);
}
else if (lv[p->v]!=(lv[u]^p->w))
{
flag=false;
return ;
}
}
int main()
{
freopen("line.in","r",stdin);
freopen("line.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int N,M;
scanf("%d%d",&N,&M);
mem=pool;
flag=true;
tot=0;
memset(adj,0,sizeof(adj));
memset(lv,-1,sizeof(lv));
memset(belong,-1,sizeof(belong));
for(int i=0;i<M;i++)
{
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
if (u!=v)
addedge(u,v,k);
else if (k!=0)
flag=false;
}
for(int i=1;i<=N && flag;i++)
if (lv[i]==-1)
{
lv[i]=0;
tot++;
dfs(i);
}
if (flag)
if (belong[1]==belong[N])
printf("%d\n",lv[1]^lv[N]);
else
printf("2\n");
else
printf("No Answer\n");
}
return 0;
}