2809人阅读
数据结构（202）
算法（604）
分类：&&157人阅读&&&
&&1、欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。
&&2、 无向图中存在欧拉回路的条件：每个点的度数均为偶数。
& 3、有向图中存在欧拉回路的条件：每个点的入度 = 出度。
& 4、欧拉路径比欧拉回路要求少一点：无向图中存在欧拉路径的条件：每个点的度数均为偶数或者有且仅有2个度数为奇数的点。
& 5、有向图中存在欧拉路径的条件：除了2个点外，其余的点入度=出度，且在这2个点中，一个点的入度比出度大1，另一个出度比入度大1。
& 6、欧拉路径的输出：经典的套圈算法。
求解一般图欧拉回路的基本算法
对于欧拉回路，有一个基本的算法：对于无向图，每个点的度都是偶数，则图中有欧拉回路存在；对于有向图，只要每个点的出度等于入度，则图中有欧拉回路存在。
求解混合图欧拉回路的一般方法
1、随意定向
在混合图中，对于双向边的处理除了拆边之外，还有任意定向。先对全图的双向边进行任意定向，接着使用上文的欧拉回路算法，很显然，无法得到结果。但是通过这一步，至少可以确定这样一件事实，如果一个点的出度加入度一定是奇数的话，那么这个图一定没有欧拉回路。
而随意定向是没有依据的，但是可以使用这样的随机化处理方法，再使用恰当的调整方法构造出解。
2、自调整方法
所谓的自调整方法就是将其中的一些边的方向调整回来，使所有的点的出度等于入度。但是有一条边的方向改变后，可能会改变一个点的出度的同时改变另一个点的入度，相当于一条边制约着两个点。同时有些点的出度大于入度，迫切希望它的某些点出边转向；而有些点的入度大于出度，迫切希望它的某些入边转向。这两条边虽然需求不同，但是他们之间往往一条边转向就能同时满足二者。
具体步骤：
1、另x = |入度-出度|/2；对于不同的点有不同的x值，这个x值代表它们在邻接表中相应调整x条就能让出度等于入度。
2、以把图中的点转换为一个二分图，每个点的x值就是它们的点权。
3、置源点S向所有出度&入度的点连边；设置汇点T，所有入度大于出度的点连边，将各自的点权转换为边权。
4、最后将原图中所有暂时定向的无向边加上一个1的容量，方向不变，而有向边不能改变方向，不需连边。
可以发现，从源点S出发的一个单位流将会一个“无向边”的容量变为0，使得两端的点权各自减1，其实这就是在模拟一次对无向边方向的调整。当把图建好后，依靠最大流性质可以最大可能地无冲突调整边的方向，并最终使得每个点的点容量都达到满流。
最后，还要对那些图中出度等于入度的点做适当分析，它们作为一个“中间点”，由于流平衡性质，不会留下任何流量值，对于那些真正需要调整的点不会带来任何影响。
最后，如何得到答案？那就是检查从源点出发的每条边是否都满流，如果有一条边没有满流，说明有一个点没有调整到入度等于出度，于是整个图不存在欧拉回路。
具体的题目有: POJ 1637、 Hdu 3472
附POJ 1637 代码：
POJ 1637 混合图欧拉回路的判定
欧拉通路 (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连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
-----------------------------------------------------------------------------------
注意最大流应该等于的是 所有的出度大于入度的点上的x之和
#include&iostream&&
#include&algorithm&&
#include&iomanip&&
#include&cstring&&
#include&string&&
#include&cstdio&&
#include&cmath&&
#include&queue&&
#include&map&&
#include&set&&
#define MAXN 2222&
#define MAXM 222222&
#define INF &
struct node&
&&&&&& // vertex&
&&&&&& // capacity&
&&&&& // current flow in this arc&
&&& int next,&
}edge[MAXM];&
int dist[MAXN], numbs[MAXN], src, des,&
int head[MAXN],&
void add(int x, int y, int c)&
{&&&&&& //e记录边的总数&
&&& edge[e].ver =&
&&& edge[e].cap =&
&&& edge[e].flow = 0;&
&&& edge[e].rev = e + 1;&&&&&&& //反向边在edge中的下标位置&
&&& edge[e].next = head[x];&& //记录以x为起点的上一条边在edge中的下标位置&
&&& head[x] = e++;&&&&&&&&&& //以x为起点的边的位置&
&&& //反向边&
&&& edge[e].ver =&
&&& edge[e].cap = 0;& //反向边的初始网络流为0&
&&& edge[e].flow = 0;&
&&& edge[e].rev = e - 1;&
&&& edge[e].next = head[y];&
&&& head[y] = e++;&
void rev_BFS()&
&&& int Q[MAXN], qhead = 0, qtail = 0;&
&&& for(int i = 1; i &= ++i)&
&&&&&&& dist[i] = MAXN;&
&&&&&&& numbs[i] = 0;&
&&& Q[qtail++] =&
&&& dist[des] = 0;&
&&& numbs[0] = 1;&
&&& while(qhead != qtail)&
&&&&&&& int v = Q[qhead++];&
&&&&&&& for(int i = head[v]; i != -1; i = edge[i].next)&
&&&&&&& {&
&&&&&&&&&&& if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] & MAXN)&
&&&&&&&&&&& dist[edge[i].ver] = dist[v] + 1;&
&&&&&&&&&&& ++numbs[dist[edge[i].ver]];&
&&&&&&&&&&& Q[qtail++] = edge[i].&
&&&&&&& }&
void init()&
&&& e = 0;&
&&& memset(head, -1, sizeof(head));&
int maxflow()&
&&& int u, totalflow = 0;&
&&& int Curhead[MAXN], revpath[MAXN];&
&&& for(int i = 1; i &= ++i)Curhead[i] = head[i];&
&&& while(dist[src] & n)&
&&&&&&& if(u == des)&&&& // find an augmenting path&
&&&&&&& {&
&&&&&&&&&&& int augflow = INF;&
&&&&&&&&&&& for(int i = i != i = edge[Curhead[i]].ver)&
&&&&&&&&&&&&&&& augflow = min(augflow, edge[Curhead[i]].cap);&
&&&&&&&&&&& for(int i = i != i = edge[Curhead[i]].ver)&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&& edge[Curhead[i]].cap -=&
&&&&&&&&&&&&&&& edge[edge[Curhead[i]].rev].cap +=&
&&&&&&&&&&&&&&& edge[Curhead[i]].flow +=&
&&&&&&&&&&&&&&& edge[edge[Curhead[i]].rev].flow -=&
&&&&&&&&&&& }&
&&&&&&&&&&& totalflow +=&
&&&&&&&&&&& u =&
&&&&&&& }&
&&&&&&& for(i = Curhead[u]; i != -1; i = edge[i].next)&
&&&&&&&&&&& if(edge[i].cap & 0 && dist[u] == dist[edge[i].ver] + 1)&
&&&&&&& if(i != -1)&&&& // find an admissible arc, then Advance&
&&&&&&& {&
&&&&&&&&&&& Curhead[u] =&
&&&&&&&&&&& revpath[edge[i].ver] = edge[i].&
&&&&&&&&&&& u = edge[i].&
&&&&&&& }&
&&&&&&& else&&&&&&& // no admissible arc, then relabel this vertex&
&&&&&&& {&
&&&&&&&&&&& if(0 == (--numbs[dist[u]]))&&& // GAP cut, Important!&
&&&&&&&&&&& Curhead[u] = head[u];&
&&&&&&&&&&& int mindist =&
&&&&&&&&&&& for(int j = head[u]; j != -1; j = edge[j].next)&
&&&&&&&&&&&&&&& if(edge[j].cap & 0)mindist = min(mindist, dist[edge[j].ver]);&
&&&&&&&&&&& dist[u] = mindist + 1;&
&&&&&&&&&&& ++numbs[dist[u]];&
&&&&&&&&&&& if(u != src)&
&&&&&&&&&&&&&&& u = edge[revpath[u]].&&& // Backtrack&
&&&&&&& }&
int ind[MAXN], outd[MAXN];&
int xx[MAXM], yy[MAXM], cc[MAXM];&
int main()&
&&& int T,&
&&& scanf(&%d&, &T);&
&&& while(T--)&
&&&&&&& init();&
&&&&&&& memset(ind, 0, sizeof(ind));&
&&&&&&& memset(outd, 0, sizeof(outd));&
&&&&&&& scanf(&%d%d&, &n, &m);&
&&&&&&& for(int i = 1; i &= i++)&
&&&&&&& {&
&&&&&&&&&&& scanf(&%d%d%d&, &xx[i], &yy[i], &cc[i]);&
&&&&&&&&&&& ind[yy[i]]++;&
&&&&&&&&&&& outd[xx[i]]++;&
&&&&&&& }&
&&&&&&& bool flag =&
&&&&&&& for(int i = 1; i &= i++)&
&&&&&&&&&&& if((outd[i] - ind[i]) % 2 != 0)&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&& flag =&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& }&
&&&&&&& if(!flag) {printf(&impossible\n&);}&
&&&&&&& int flow = 0;&
&&&&&&& for(int i = 1; i &= i++)&
&&&&&&& {&
&&&&&&&&&&& if(xx[i] == yy[i] || cc[i])&
&&&&&&&&&&& add(xx[i] + 1, yy[i] + 1, 1);&
&&&&&&& }&
&&&&&&& src = 1, des = n + 2;&
&&&&&&& for(int i = 1; i &= i++)&
&&&&&&& {&&&
&&&&&&&&&&& int x = abs(outd[i] - ind[i]) / 2;&
&&&&&&&&&&& if(outd[i] & ind[i]) add(src, i + 1, x), flow +=&
&&&&&&&&&&& else if(ind[i] & outd[i]) add(i + 1, des, x);&
&&&&&&& }&
&&&&&&& n = n + 2;&
&&&&&&& rev_BFS();&
&&&&&&& if(maxflow() == flow) printf(&possible\n&);&
&&&&&&& else printf(&impossible\n&);&
&&& return 0;&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3975229次
积分：35640
积分：35640
排名：第110名
原创：22篇
转载：1920篇
评论：480条
(37)(14)(28)(148)(78)(74)(36)(80)(90)(42)(139)(241)(117)(357)(181)(63)(56)(57)(5)(47)(1)(30)(23)深圳市艾秀信息技术有限公司
All Rights Reserved
&粤网文[号 &&&&&&&当前位置：&gt
月销量10件
一淘网为您找到tot插座产品的详细资讯，实时报价，价格行情，tot插座商品分类,论坛问答/求购等相关产品信息。
增值电信业务经营许可证：浙B2-}