沒有想到網絡流還能解決這一類問題，完全想不到@_@
一開始把所有的無向邊制定任意方向有當做有向邊看，然后統計每個點的入度和出度。以前有向圖的歐拉回路判定是每個點的入讀都等于出度，這樣可以保證可以回到起點，現在在一些邊可以調換方向的情況下，所有定點的入度和出度之差必定為偶數，因為調換任意一條邊的方向都會使兩個定點的入度和出度變化2，所以要構成一個歐拉回路所有點的入度和出度之差都為偶數，并設差為deg。
現在問題轉化成了能否通過改變一些邊的方向來是的所有點的入度出度都為0，因為有向邊的方向已經確定，不用理會，把他們全部都刪去。剩下的邊中如果有出度大于入度的，肯定要調換-deg/2條邊來使其變成0，建立源點到這些點的邊，容量為-deg/2，同理，有出入大于入度的，就建立這些點到匯點的邊，容量同樣為deg/2。其他的邊容量都為1，然后做一遍最大流，如果流量和需要調換的邊數相等，即源點出去的邊全部都滿載，就有歐拉回路存在，否則不存在歐拉回路。
為什么這樣子是成立的，我的想法是這樣的，除了連接源點和匯點的邊之外，其他的邊的容量都為1，1的流量對應的就是一條邊，源點連接到一個點的時候的容量為t，如果滿載相當于這個點出發的t條邊滿載，相當于調換了t條邊，但是這樣子會影響后面的邊的度，不過因為流會一直流到匯點，中途所有的滿載的邊都是要調換的，所以中間原本度為0的點的度其實到最后不會改變。
#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() {//建立層次網絡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;//判斷入度出度之差是否為偶數for(int i = 1;i <= n;i++) {deg[i] = incnt[i] - outcnt[i];if(deg[i] & 1) return false;}//建立容量網絡for(int i = 1;i <= n;i++) {//如果入度小于出度,建立從起點到這個點的邊，容量為deg/2if(deg[i] < 0) adde(s,i,-deg[i] / 2);//如果出度大于入讀，建立從當前點到匯點的邊，容量同樣為deg/2if(deg[i] > 0) adde(i,t,deg[i] / 2);}//計算最大流dinic();//判斷從源點出發的所有邊是否滿流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;
}
-命名空間)
