poj1637 Sightseeing tour 网络流混合图的欧拉回路

题目链接: http://poj.org/problem?id=1637

题意：给出N个点，M条路。路有些是双向边，有些是单向边。求是否能找到一个起点，使之遍历所有路正好一次并最后回到起点。

即判断这个图是否是欧拉回路。

思路：

参考：http://www.cnblogs.com/kuangbin/p/3537525.html

要求是否存在欧拉回路。

首先判断整个图是否相连，如果不连通，肯定不存在。

欧拉回路满足条件，每个点的出度 = 入度。

但因为有双向边的存在，事实上找欧拉回路就是要确定双向边的方向。即定向双向边，如果有一种定向使得整个图为一张有向欧拉图，那么就满足条件

设D[i] = out[i] - in[i]，即i这个点的出度 - 入度。

要满足条件，则对于所有点D[i] = 0.

一开始先人为规定无向边的方向，然后求出D[i]。

假如说原来的边(i->j)改变方向后，对于点i来说，i的出度减少1，i的入度增加1.即out[i]->out[i]-1 in[i]->in[i]+1。

所以D[i] = out[i] - in[i] = out[i] - 1 - in[i] - 1 减少了2.

反之则增加2.

因为最终需要满足的是D[i] = 0,所以如果开始时D[i]是奇数，那么最终肯定不会满足条件。

排除D[i]是奇数的情况后，一开始先人为的规定无向边的方向，如(i->j)。并且在图中连一条边(i->j)，容量为1，表示之后能改变一次方向。

对于有向边则无需连边。

增设源点s,汇点t。

然后对于每个点，如果D[i] > 0,则在s到i，连一条边，容量为D[i]/2.

如果D[i] < 0,则在i到t，连一条边，容量为-D[i]/2.

考虑网络中的一条增广路径S-->i-->...-->j-->T，将这条从i到j的路径在G'中全部反向，则：i 的入度加1出度减1，j的入度减1出度加1。

路径中其它点的入度出度均不变。而i是和S相连的，因此初始D[i]>0，即i的出度大于入度，故这样反向之后D[i]减少2；

同理，j是和T相连的，这样反向之后D[j]增加2。因此，若最大流中边<S, i>满流（流量为初始D[i]/2），此时D[i]值就变成了0，也就是i的入度等于出度。

因此只要使所有S引出的边全部满流，所有初始D 值>0的点的D值将等于0，又因为将边变向后所有点的D值之和不变，所有初始D值小于0的点的D值也将等于0。

而初始D值等于0的D点既不与S相连也不与T相连，所以它们是网络中的中间点，而中间点的流入量等于流出量，故它们的入度和出度一直不变，即D值一直为0。因此，整个图G'成为欧拉图。

求欧拉通路：

因为对于欧拉通路来说，除了通路的起点和终点外的所有点仍满足D[i] = 0。且起点和终点的D[i]必为奇数。

所以先求出所有D[i],如果刚好有两个点的D[i]为奇数，则有可能存在欧拉通路。

如果D[i] > 0 && D[j] < 0 则i为起点，j为终点。连边j->i

如果D[i] < 0 && D[j] > 0 则j为起点，i为终点。连边i->j

然后求欧拉回路。

  1 //#include <bits/stdc++.h>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <string>
  6 #include <vector>
  7 #include <queue>
  8 using namespace std;
  9 #define maxn 210
 10 const int inf = 0x3f3f3f3f;
 11 int min(int a, int b)
 12 {
 13     return a<b?a:b;
 14 }
 15 struct Edge
 16 {
 17     int from, to, cap, flow;
 18     Edge(int f, int t, int c, int fl)
 19     {
 20         from = f; to = t; cap = c; flow = fl;
 21     }
 22 };
 23 vector <Edge> edges;
 24 vector <int> G[maxn];
 25 int d[maxn], vis[maxn], cur[maxn];
 26 int s, t, n, m;
 27 void AddEdge(int from, int to, int cap)
 28 {
 29     edges.push_back(Edge(from, to, cap, 0));
 30     edges.push_back(Edge(to, from, 0, 0));
 31     m = edges.size();
 32     G[from].push_back(m-2);
 33     G[to].push_back(m-1);
 34 }
 35 bool bfs()
 36 {
 37     memset(vis, 0, sizeof(vis));
 38     d[s] = 0;
 39     vis[s] = 1;
 40     queue <int> q;
 41     q.push(s);
 42     while(!q.empty())
 43     {
 44         int u = q.front();
 45         q.pop();
 46         for(int i = 0; i < G[u].size(); i++)
 47         {
 48             Edge &e = edges[G[u][i]];
 49             if(!vis[e.to] && e.cap > e.flow)
 50             {
 51                 vis[e.to] = 1;
 52                 d[e.to] = d[u] + 1;
 53                 q.push(e.to);
 54                 
 55             }
 56         }
 57     }
 58     return vis[t];
 59 }
 60 int dfs(int x, int a)
 61 {
 62     if(x == t || a == 0) return a;
 63     int flow = 0, f;
 64     for(int &i = cur[x]; i < G[x].size(); i++)
 65     {
 66         Edge &e = edges[G[x][i]];
 67         if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(e.cap - e.flow, a))) > 0)
 68         {
 69             e.flow += f;
 70             edges[G[x][i]^1].flow -= f;
 71             flow += f;
 72             a -= f;
 73             if(a == 0) break;
 74             
 75         }
 76     }
 77     return flow;
 78 }
 79 int MaxFlow()
 80 {
 81     int flow = 0;
 82     while(bfs())
 83     {
 84         memset(cur, 0, sizeof(cur));
 85         flow += dfs(s, inf);
 86     }
 87     return flow;
 88 }
 89 int T, N, M;
 90 int in[maxn], out[maxn], D[maxn];
 91 int main()
 92 {
 93     scanf("%d", &T);
 94     while(T--)
 95     {
 96         edges.clear();
 97         scanf("%d%d", &N, &M);
 98         for(int i = 0; i <= N+1; i++) G[i].clear();
 99         s = 0; t = N+1;
100         memset(in, 0, sizeof(in));
101         memset(out, 0, sizeof(out));
102         for(int i = 1; i <= M; i++)
103         {
104             int a, b, c;
105             scanf("%d%d%d", &a, &b, &c);
106             if(c == 0)
107             {
108                 out[a]++; in[b]++;
109                 AddEdge(a, b, 1);
110             }
111             else if(c == 1)
112             {
113                 out[a]++; in[b]++;
114             }
115         }
116         bool flag = true;
117         for(int i = 1; i <= N; i++)
118         {
119             D[i] = out[i] - in[i];
120             if(D[i]%2)
121             {
122                 flag = false; break;
123             }
124             if(D[i] > 0) AddEdge(s, i, D[i]/2);
125             else if(D[i] < 0) AddEdge(i, t, -D[i]/2);
126         }
127         if(flag == false)
128         {
129             printf("impossible
"); continue;
130         }
131         int flow = MaxFlow();
132         flag = true;
133         for(int i = 0; i < m; i++)
134         {
135             Edge &e = edges[i];
136             if(e.from == s & e.cap != e.flow)
137             {
138                 flag = false;
139                 break;
140             }
141         }
142         if(flag == true) printf("possible
");
143         else printf("impossible
");
144     }
145     return 0;
146 }

poj1637 Sightseeing tour 网络流 混合图的欧拉回路

poj1637 Sightseeing tour 网络流混合图的欧拉回路