以下解释来源于其他牛人：

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是
9
变出），就能保证出=入。如果每个点都是出=入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出=入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入>出的点u，连接边(u, t)、容量为x，对于出>入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度=出度的欧拉图。
由于是满流，所以每个入>出的点，都有x条边进来，将这些进来的边反向，OK，入=出了。对于出>入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出>入，和t连接的条件是入>出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入=出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。

如果这道题用矩阵，需要注意两点直接可能有有条边，容量要相加。

 

 

#include <stdio.h>
#include <string.h>
#define MAXN	210
#define MIN( a, b ) (a) > (b) ? (b) : (a)

int ent[MAXN];
int map[MAXN][MAXN], flow[MAXN][MAXN];

int EK( int num, int s, int t )
{
	int my_queue[MAXN], head, tail;
	int pre[MAXN], min_flow[MAXN];
	int ans = 0, i, k;
	memset( flow, 0, sizeof( flow ) );
	while ( 1 )
	{
		head = 0; tail = 1;
		my_queue[0] = s;
		memset( pre, -1, sizeof( pre ) );
		min_flow[s] = 0x7fffffff;
		pre[s] = -2;
		while ( head < tail )
		{
			k = my_queue[head++];
			for ( i = 0; i < num; ++i )
			{
				if ( pre[i]==-1 && flow[k][i]<map[k][i] )
				{
					my_queue[tail++] = i;
					pre[i] = k;
					min_flow[i] = MIN( min_flow[k], ( map[k][i]-flow[k][i] ) );
				}
			}
			if ( pre[t] != -1 )
			{
				k = t;
				while ( pre[k] >= 0 )
				{
					flow[pre[k]][k] += min_flow[t];
					flow[k][pre[k]] = -flow[pre[k]][k];
					k = pre[k];
				}
				break;
			}
		}
		if ( pre[t] == -1 ) return ans;
		else ans += min_flow[t];
	}
}

int main()
{
	int n, m, x, y, z, flag, cases;

	//freopen( "main.in", "r", stdin );

	scanf( "%d", &cases );
	while ( cases-- )
	{
		flag = 1;
		memset( ent, 0, sizeof( ent ) );
		memset( map, 0, sizeof( map ) );
		scanf( "%d%d", &n, &m );
		while ( m-- )
		{
			scanf( "%d%d%d", &x, &y, &z );
			ent[x]--; ent[y]++;
			if ( z == 0 ) map[x][y]++;
		}
		for ( z = 0, y = 1; y <= n && flag; ++y )
		{
			if ( ent[y] % 2 ) flag = 0;
			x = ent[y] / 2;
			if ( x > 0 )
			{
				map[y][n+1] = x; z += x;
			}
			else
				map[0][y] = -x;
		}
		if ( flag )	x = EK( n+2, 0, n+1 );
		if ( flag && x == z )
			printf( "possible\n" );
		else
			printf( "impossible\n" );
	}
	return 0;
}

 

#include <stdio.h>
#include <string.h>
#define MAXN 210
#define MAXM 2500

int MIN( int a, int b )
{
	return a > b ? b : a;
}

typedef struct node
{
	int f, c, u, v;
	struct node *rev, *next;
}tnode, *pnode;
tnode	edge[MAXM];
pnode	g[MAXN], pre[MAXN];
int		now, ent[MAXN];

void addEdge( int u, int v, int c, int k )
{
	pnode p = &edge[now];
	p->c = c; p->u = u; p->v = v;
	p->next = g[u];
	if ( k != -1 ) p->rev = &edge[k];
	g[u] = p; now++;
}

int EK( int num, int sour, int sink )
{
	int my_queue[MAXN], head, tail;
	int min_flow[MAXN], ans = 0;
	pnode p;

	while ( 1 )
	{
		head = 0; tail = 1;
		my_queue[0] = sour;
		memset( pre, 0, sizeof( pre ) );
		min_flow[sour] = 0x7fffffff;
		while ( head < tail )
		{
			int t = my_queue[head++];
			for ( p = g[t]; p; p = p->next )
			if ( pre[p->v] == 0 && p->f < p->c )
			{
				my_queue[tail++] = p->v;
				pre[p->v] = p;
				min_flow[p->v] = MIN( min_flow[t], ( p->c - p->f ) );
			}
			if ( pre[sink] )
			{
				for ( p = pre[sink]; p; p = pre[p->u] )
				{
					p->f += min_flow[sink];
					if ( p->rev ) p->rev->f = -p->f;
				}
				break;
			}
		}
		if ( pre[sink] == 0 ) return ans;
		else ans += min_flow[sink];
	}
}

int main()
{
	int n, m, x, y, z, flag, cases;
	//freopen( "main.in", "r", stdin );
	scanf( "%d", &cases );
	while ( cases-- )
	{
		flag = 1; now = 0;
		memset( ent, 0, sizeof( ent ) );
		memset( edge, 0, sizeof( edge ) );
		memset( g, 0, sizeof( g ) );
		scanf( "%d%d", &n, &m );
		while ( m-- )
		{
			scanf( "%d%d%d", &x, &y, &z );
			ent[x]--; ent[y]++;
			if ( z == 0 )
			{
				addEdge( x, y, 1, now+1 );
				addEdge( y, x, 0, now-1 );
			}
		}
		for ( z = 0, y = 1; y <= n && flag; ++y )
		if ( ent[y] != 0 )
		{
			if ( ent[y] & 1 ) flag = 0;
			x = ent[y] / 2;
			if ( x > 0 )
			{
				addEdge( y, n+1, x, -1 );
				z += x;
			}
			else
				addEdge( 0, y, -x, -1 );
		}
		if ( flag )	x = EK( n+2, 0, n+1 );
		if ( flag && x == z )
			printf( "possible\n" );
		else
			printf( "impossible\n" );
	}
	return 0;
}

 

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter