记录编号 26980 评测结果 AAAAAAAAAA
题目名称 线段 最终得分 100
用户昵称 GravatarPurpleShadow 是否通过 通过
代码语言 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;
}