本文主要是介绍POJ 1637 Sightseeing tour(混合欧拉回路，网络流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意： 给你一个图，一些边(有单向边和双向边)问是否有混合欧拉回路(每个边只走一次，起点终点相同).开始我们可以用点的入度出度检测一下，把双向边任意指定方向，如果某点的出度入度之差为奇数，肯定不会构成欧拉回路的。
如果都为偶数，我们就要检测这些双向边能否使得没电入度==出度了。 建图： 单向边不用考虑，双向边按照开始任意指定的方向建边，容量为1. 一个点如果出度>入度，连边 (源点s, i,出入度之差/2),如果入度>出度，连边(i, 汇点T,出入度之差/2).
如果满流，证明可以分配双向边使得每个点入度==出度。
其实跑完最大流后的流量分配情况说明了双向边的方向选择。
由于是满流，所以每个入>出的点，都有 x 条边进来，将这些进来的边反向，入=出了。对于出>入的点亦然。对于没有和s也没和t连接的点，自然早在开始就已经满足入=出了。中间点流量不允许有累积的，进去多少就出来多少，反向之后，自然仍保持平衡。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 1000000000
#define N 222
int t, n, m, tot, hh[N], lev[N], S, T;
int in[N], out[N];
struct node
{int u, v, w, next;
};
node edge[1000001];
struct nod
{int u, v, flag;
}ee[2111];
void init()
{tot = 0;memset(hh, -1, sizeof(hh));
}
void add(int u, int v, int w)
{edge[tot].u = u; edge[tot].v = v;edge[tot].w = w; edge[tot].next = hh[u];hh[u] = tot++;
}
int bfs()
{queue<int > Q;memset(lev, -1, sizeof(lev));Q.push(S);lev[S] = 0;while(!Q.empty()) {int u = Q.front(); Q.pop();for(int i= hh[u]; i!= -1; i = edge[i].next) {int v = edge[i].v, w = edge[i].w;if(w && lev[v] == -1) {Q.push(v); lev[v] = lev[u] + 1;}}}return lev[T] != -1;
}
int dfs(int u, int flow)
{if(u == T) return flow;int tmp = flow, ad;for(int i= hh[u]; i!=-1; i = edge[i].next) {int v= edge[i].v;if(lev[v] == lev[u]+1 && edge[i].w && tmp>0) {ad = dfs(v, min(edge[i].w, tmp));if(!tmp) break;edge[i].w -= ad;edge[i^1].w +=ad;tmp -= ad;}}if( ad == 0) lev[u] = -1;return flow - tmp;
}
int dinic()
{int ret = 0, tmp;while(bfs()) {while(tmp = dfs(S, INF)) ret += tmp;}return ret ;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEscanf("%d", &t);while(t--) {scanf("%d%d", &n, &m);init();memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));for(int i = 1; i <= m; i++) {scanf("%d%d%d", &ee[i].u, &ee[i].v, &ee[i].flag);in[ee[i].v] ++; out[ee[i].u] ++;}int ff = 0;for(int i=1; i<=n; i++) {if(abs(in[i] - out[i]) % 2) {ff = 1; break;}}if(ff) {printf("impossible\n");continue;}S = 0; T = n + 1;for(int i = 1; i <= m; i++) {if( !ee[i].flag) {add(ee[i].u, ee[i].v, 1);add(ee[i].v, ee[i].u, 0);}}int aa = 0;for(int i = 1; i <= n; i++) {int ww = (in[i] - out[i]) / 2;if(!ww) continue;else if(ww > 0) {add(i, T, ww);add(T, i, 0);}else {ww = - ww;add(S, i, ww); add(i, S, 0); aa += ww;}}int ans = dinic() ;if(ans >= aa) {printf("possible\n");}else {printf("impossible\n");}}return 0;
}这篇关于POJ 1637 Sightseeing tour(混合欧拉回路，网络流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
