比赛 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;
}