沒有想到網(wǎng)絡(luò)流還能解決這一類問題，完全想不到@_@

一開始把所有的無向邊制定任意方向有當(dāng)做有向邊看，然后統(tǒng)計(jì)每個(gè)點(diǎn)的入度和出度。以前有向圖的歐拉回路判定是每個(gè)點(diǎn)的入讀都等于出度，這樣可以保證可以回到起點(diǎn)，現(xiàn)在在一些邊可以調(diào)換方向的情況下，所有定點(diǎn)的入度和出度之差必定為偶數(shù)，因?yàn)檎{(diào)換任意一條邊的方向都會(huì)使兩個(gè)定點(diǎn)的入度和出度變化2，所以要構(gòu)成一個(gè)歐拉回路所有點(diǎn)的入度和出度之差都為偶數(shù)，并設(shè)差為deg。

現(xiàn)在問題轉(zhuǎn)化成了能否通過改變一些邊的方向來是的所有點(diǎn)的入度出度都為0，因?yàn)橛邢蜻叺姆较蛞呀?jīng)確定，不用理會(huì)，把他們?nèi)慷紕h去。剩下的邊中如果有出度大于入度的，肯定要調(diào)換-deg/2條邊來使其變成0，建立源點(diǎn)到這些點(diǎn)的邊，容量為-deg/2，同理，有出入大于入度的，就建立這些點(diǎn)到匯點(diǎn)的邊，容量同樣為deg/2。其他的邊容量都為1，然后做一遍最大流，如果流量和需要調(diào)換的邊數(shù)相等，即源點(diǎn)出去的邊全部都滿載，就有歐拉回路存在，否則不存在歐拉回路。

為什么這樣子是成立的，我的想法是這樣的，除了連接源點(diǎn)和匯點(diǎn)的邊之外，其他的邊的容量都為1，1的流量對應(yīng)的就是一條邊，源點(diǎn)連接到一個(gè)點(diǎn)的時(shí)候的容量為t，如果滿載相當(dāng)于這個(gè)點(diǎn)出發(fā)的t條邊滿載，相當(dāng)于調(diào)換了t條邊，但是這樣子會(huì)影響后面的邊的度，不過因?yàn)榱鲿?huì)一直流到匯點(diǎn)，中途所有的滿載的邊都是要調(diào)換的，所以中間原本度為0的點(diǎn)的度其實(shí)到最后不會(huì)改變。

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack>using namespace std;typedef long long LL; const int maxn = 205; const int INF = INT_MAX / 3;struct Edge {int u,v,cap;Edge(int u,int v,int cap):u(u),v(v),cap(cap) {} };int n,m,incnt[maxn],outcnt[maxn]; int deg[maxn],s,t; vector<Edge> edges; vector<int> e[maxn];void adde(int u,int v,int w) {int m = edges.size();edges.push_back(Edge(u,v,w));edges.push_back(Edge(v,u,0));e[u].push_back(m);e[v].push_back(m ^ 1); }int level[maxn],q[maxn * 2],qs,qe; bool bfs() {//建立層次網(wǎng)絡(luò)memset(level,0,sizeof(level));level[s] = 1;qs = qe = 0;q[qe++] = s;while(qs < qe) {int now = q[qs++],nm = e[now].size();if(now == t) break;for(int i = 0;i < nm;i++) {Edge &ne = edges[e[now][i]];if(ne.cap && level[ne.v] == 0) {level[ne.v] = level[now] + 1;q[qe++] = ne.v;}}}return level[t]; }int dfs(int now,int alpha) {if(now == t) return alpha;int sum = 0,nm = e[now].size();for(int i = 0;i < nm;i++) {Edge &ne = edges[e[now][i]];if(level[now] + 1 == level[ne.v] && ne.cap && alpha) {int ret = dfs(ne.v,min(alpha,ne.cap));ne.cap -= ret; edges[e[now][i] ^ 1].cap += ret;sum += ret; alpha -= ret;}}if(sum == 0) level[now] = -1;return sum; }void dinic() {while(bfs()) dfs(s,INF); }bool solve() {s = 0; t = n + 1;//判斷入度出度之差是否為偶數(shù)for(int i = 1;i <= n;i++) {deg[i] = incnt[i] - outcnt[i];if(deg[i] & 1) return false;}//建立容量網(wǎng)絡(luò)for(int i = 1;i <= n;i++) {//如果入度小于出度,建立從起點(diǎn)到這個(gè)點(diǎn)的邊，容量為deg/2if(deg[i] < 0) adde(s,i,-deg[i] / 2);//如果出度大于入讀，建立從當(dāng)前點(diǎn)到匯點(diǎn)的邊，容量同樣為deg/2if(deg[i] > 0) adde(i,t,deg[i] / 2);}//計(jì)算最大流dinic();//判斷從源點(diǎn)出發(fā)的所有邊是否滿流int m = e[s].size();for(int i = 0;i < m;i++) {if(edges[e[s][i]].cap != 0) return false;}return true; }int main() {int T; scanf("%d",&T);while(T--) {scanf("%d%d",&n,&m);edges.clear();for(int i = 0;i <= n + 1;i++) e[i].clear();memset(incnt,0,sizeof(incnt));memset(outcnt,0,sizeof(outcnt));for(int i = 1;i <= m;i++) {int u,v,c; scanf("%d%d%d",&u,&v,&c);//先將無向邊全部作為有向邊處理incnt[v]++; outcnt[u]++;//無向邊存起來if(c == 0) adde(u,v,1);}if(solve()) puts("possible");else puts("impossible");}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/rolight/p/3871431.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1637 Sightseeing tour 混合图欧拉回路存在性判断的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。