POJ 1637 Sightseeing tour - nazgul's Blog
POJ 1637 Sightseeing tour
以下解释来源于其他牛人:
把该图的无向边随便定向,计算每个点的入度和出度。如果有某个点出入度之差为奇数,那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度,也就是总度数为偶数,存在奇数度点必不能有欧拉回路。
好了,现在每个点入度和出度之差均为偶数。那么将这个偶数除以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; }