/*1.存在邻接边为奇数的点必不能构成欧拉回路*/
/*2.任一点的入度和出度不能大于这点总邻接边的一半*/
/*3.满足上述条件的就能通过指定双向边的方向构成欧拉回路*/
/*上述看法有错吗？如有，举个反例*/
#include<iostream>
using namespace std;
#define N 202
int in[N],out[N],edge[N],v;
bool Euler()
{
	int i;
	for(i=1;i<=v;i++){
		if(edge[i]%2)//1
			return false;
	}
	for(i=1;i<=v;i++){
		if(!((out[i]<=edge[i]/2)&&(in[i]<=edge[i]/2)))//2
			return false;
	}
	return true;//3
}
int main()
{
	int t,i,e,fr,to,dr;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&v,&e);
		for(i=1;i<=v;i++)
			edge[i]=in[i]=out[i]=0;
		for(i=0;i<e;i++)
		{
			scanf("%d%d%d",&fr,&to,&dr);
			if(dr){
				out[fr]++;
				in[to]++;
			}
			edge[fr]++;
			edge[to]++;
		}
		if(Euler()) printf("possible\n");
		else printf("impossible\n");
	}
	return 0;
}

• Re:我有一个简单的想法，大家看看 (16) qitaishui 2012-05-27 21:22:40
  • Re:我有一个简单的想法，大家看看 (118) zjkmxy 2014-07-31 08:51:32