思路是别人的,代码是自己的,自己的模版题。
1 定义
欧拉通路 (Euler tour)——通过图中每条边一次且仅一次,
并且过每一顶点的通路。欧拉回路 (Euler circuit)——通过图中每条边一次且仅一次,并且过每一顶点的回路。欧拉图——存在欧拉回路的图。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为:G 连通,G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。G有欧拉回路(G为欧拉图):G连通,G中均为偶度顶点。
3 有向图是否具有欧拉通路或回路的判定
D有欧拉通路:D连通,除两个顶点外,其余顶点的入度均等于出度,这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。D有欧拉回路(D为欧拉图):D连通,D中所有顶点的入度等于出度。
4 混合图。混合图也就是无向图与有向图的混合,即图中的边既有有向边也有无向边。
5 混合图欧拉回路
混合图欧拉回路用的是网络流。把该图的无向边随便定向,计算每个点的入度和出度。如果有某个点出入度之差为奇数,那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度,也就是总度数为偶数,存在奇数度点必不能有欧拉回路。现在每个点入度和出度之差均为偶数。将这个偶数除以2,得x。即是说,对于每一个点,只要将x条边反向(入>出就是变入,出>入就是变出),就能保证出 = 入。如果每个点都是出 = 入,那么很明显,该图就存在欧拉回路。现在的问题就变成了:该改变哪些边,可以让每个点出 = 入?构造网络流模型。有向边不能改变方向,直接删掉。开始已定向的无向边,定的是什么向,就把网络构建成什么样,边长容量上限1。另新建s和t。对于入 > 出的点u,连接边(u, t)、容量为x,对于出 > 入的点v,连接边(s, v),容量为x(注意对不同的点x不同。当初由于不小心,在这里错了好几次)。之后,察看是否有满流的分配。有就是能有欧拉回路,没有就是没有。查看流值分配,将所有流量非 0(上限是1,流值不是0就是1)的边反向,就能得到每点入度 = 出度的欧拉图。由于是满流,所以每个入 > 出的点,都有x条边进来,将这些进来的边反向,OK,入 = 出了。对于出 > 入的点亦然。那么,没和s、t连接的点怎么办?和s连接的条件是出 > 入,和t连接的条件是入 > 出,那么这个既没和s也没和t连接的点,自然早在开始就已经满足入 = 出了。那么在网络流过程中,这些点属于“中间点”。我们知道中间点流量不允许有累积的,这样,进去多少就出来多少,反向之后,自然仍保持平衡。
Source Code Problem: 1637 User: 1013101127 Memory: 324K Time: 110MS Language: C++ Result: Accepted Source Code #include<cstdio> #include<queue> #include<cstring> #include<iostream> #include<algorithm> #include<cstring> #include<map> #include<string> #include <stdio.h> #include <iostream> #include <string.h> #include<queue> #include<cmath> using namespace std; const int inf=1<<30; const int M=500,ME=3009; const int INF=0x3f3fffff; //******************************最小费用最大流模版(可以单独用来求最大流,输入的时候,cost=0就可以:适用于u->v,只要符合了流量限制,只要通过了就花费,还有一种是:u->v,每单位的流量必须花费对少费用(poj2159模板)) int Head[M],Next[ME],Num[ME],Flow[ME],Cap[ME],Cost[ME],vis[ME],Q[M],InQ[M],Len[M],pre_edge[M]; int top; void clear() { memset(Head,-1,sizeof(Head)); memset(Flow,0,sizeof(Flow)); memset(vis,0,sizeof(vis)); top=0; } void addedge(int u,int v,int cap,int cost) { Next[top] = Head[u]; Num[top] = v; Cap[top] = cap; Cost[top] = cost; Head[u] = top++; Next[top] = Head[v]; Num[top] = u; Cap[top] = 0; Cost[top] = -cost; Head[v] = top++; } bool SPFA(int s,int t) { fill(Len,Len+M,INF); Len[s]=0; int head = -1,tail = -1,cur; Q[++head] = s; while(head != tail) { ++tail; if(tail >= M) tail = 0 ; cur = Q[tail]; for(int i = Head[cur];i != -1;i = Next[i]) { if(Cap[i]>Flow[i] && Len[Num[i]] > Len[cur] + Cost[i]) { Len[Num[i]] = Len[cur] + Cost[i]; pre_edge[Num[i]] = i; if(!InQ[Num[i]]) { InQ[Num[i]]=true; ++head; if(head >= M) head = 0; Q[head] = Num[i]; } } } InQ[cur]=false; } return Len[t] != INF; } int solve(int s,int t) { int ans= 0; while(SPFA(s,t)) { int cur = t,minflow = INF; while(cur != s) { if(minflow > Cap[pre_edge[cur]]-Flow[pre_edge[cur]]) minflow = Cap[pre_edge[cur]]-Flow[pre_edge[cur]]; cur = Num[pre_edge[cur] ^ 1]; } cur = t ; ans+=minflow; while(cur != s) { Flow[pre_edge[cur]] += minflow; Flow[pre_edge[cur] ^ 1] -= minflow; vis[pre_edge[cur]]=1; cur = Num[pre_edge[cur] ^ 1]; } } return ans;//最大流 // int cost;//最小费用 //for(int i=0;i<top;i++) //适用于u->v,只要符合了流量限制,只要通过了就花费,不管通过多少流量 //{ // if(Flow[i]>0) // cost+=Cost[i]; //} } //**************************************************************** int n,m; int main() { int cas; cin>>cas; int u,v,c; int ind[M],outd[M]; while(cas--) { cin>>n>>m; clear(); memset(ind,0,sizeof(ind)); memset(outd,0,sizeof(outd)); for(int i=0;i<m;i++) { cin>>u>>v>>c; if(c) { outd[u]++;ind[v]++; } else { outd[u]++;ind[v]++; addedge(u,v,1,0); } } int flag=1; for(int i=1;i<=n;i++) { if(abs(ind[i]-outd[i])%2==1) { flag=0;break; } } if(!flag) {cout<<"impossible"<<endl;continue;} int start=0; int end=n+1; int sum=0; for(int i=1;i<=n;i++) { if(ind[i]>outd[i]) addedge(i,end,(ind[i]-outd[i])/2,0); else if(outd[i]>ind[i]) { addedge(start,i,(outd[i]-ind[i])/2,0); sum+=(outd[i]-ind[i])/2; } } int ans=solve(start,end); //cout<<ans<<endl; if(sum==ans) cout<<"possible"<<endl; else cout<<"impossible"<<endl; } return 0; }