poj 1637 混合欧拉回路 网络流 dinic 以及sap 算法
题意：给出一个混合图（有的边有向，有的边无向），问此图是否存在欧拉回路。
先说说欧拉回路吧，起点和终点相同，经过图G的每条边一次，且只经过一次的路径称为欧拉回路。
按照图的不同分为：无向图欧拉回路、有向图欧拉回路和混合图欧拉回路。
判断一个图是否存在欧拉回路：
1.无向图：图连通，且图中均为偶度顶点。
2.有向图：图连通，且图中所有顶点出入度相等。
3.混合图：混合图欧拉回路的判断是用网络流，实现方法：
首先对所有的无向边随便定向，之后会进行调整。然后统计每个点的出入度，如果有某个点出入度之差为奇数，则不存在欧拉回路，因为相差为奇数的话，无论如果调整边，都不能使得每个点的出入度相等。
现在每个点的出入度之差为偶数了，把这个偶数除以2,得x。则对每个顶点改变与之相连的x条边的方向就可以使得该点出入度相等。如果每个点都能达到出入度相等，自然就存在欧拉回路了。
现在问题就变成了改变哪些边的方向能让每个点出入度相等了，构造网络流模型。
有向边不能改变方向，所以不添加有向边。对于在开始的时候任意定向的无向边，按所定的方向加边，容量为1。源点向所有出>入的点连边，容量为该点的x值；所有入>出的点向汇点连边，容量为该点的x值。
建图完成了，求解最大流，如果能满流分配，则存在欧拉回路。那么哪些边改变方向才能得到欧拉回路呢？查看流量分配，所有流量非0的边就是要改变方向的边。
原理是因为满流分配，所以和源点相连的点一定都有x条边流入，将这些边反向这些点就出入度相等了，和汇点相连的亦然。没有和源、汇相连的已经出入度相等了，当然不用修改，至此欧拉回路求解完毕。
我个人的理解： 首先 上面红色的 是由于 在欧拉回路中每个点的出度都等于入度。 那么当一个点的出度增加1 那么入度一定减少1 那么他们的差依旧保持为偶数 如果不是 说明这个图不会是欧拉回路
我们把无向边随意变成有向边后 会存在有些点的入度不等于出度 ，那么我们需要改变以前的那些无向边中的部分边 使得每个点都能够出度等于入度。
如何修改那 ？ 按照上面的方式连接各个边之后 形成的图的意思 就是： 从s到所有边中找出部分边修改使得与s相连的每个点的入度等于出度 同时使得与t相连的每个点的出度等于入度
DINIC算法
#include <stdio.h>
#include <string.h>
#define VM 222
#define EM 20550
#define inf 0x3f3f3f3f
struct Edge
{
int frm,to,cap,next;
}edge[EM];
int head[VM],dep[VM],ep; //dep为点的层次
void addedge (int cu,int cv,int cw) //第一条边下标必须为偶数
{
edge[ep].frm = cu;
edge[ep].to = cv;
edge[ep].cap = cw;
edge[ep].next = head[cu];
head[cu] = ep;
ep ++;
edge[ep].frm = cv;
edge[ep].to = cu;
edge[ep].cap = 0;
edge[ep].next = head[cv];
head[cv] = ep;
ep ++;
}
int BFS (int src,int des) //求出层次图
{
int que[VM],i,front = 0,rear = 0;
memset (dep,-1,sizeof(dep));
que[rear++] = src;
dep[src] = 0;
while (front != rear)
{
int u = que[front++];
front = front%VM;
for (i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > 0&&dep[v] == -1) //容量大于0&&未在dep中
{
dep[v] = dep[u] + 1; //建立层次图
que[rear ++] = v;
rear = rear % VM;
if (v == des) //找到汇点 返回
return 1;
}
}
}
return 0;
}
int dinic (int src,int des)
{
int i,res = 0,top;
int stack[VM]; //stack为栈，存储当前增广路
int cur[VM]; //存储当前点的后继 跟head是一样的
while (BFS(src,des)) //if BFS找到增广路
{
memcpy (cur,head,sizeof (head));
int u = src; //u为当前结点
top = 0;
while (1)
{
if (u == des) //增广路已全部进栈
{
int min = inf,loc ;
for (i = 0;i < top;i ++) //找最小的增广跟并loc记录其在stack中位置
if (min > edge[stack[i]].cap) //以便退回该边继续DFS
{
min = edge[stack[i]].cap;
loc = i;
}
for (i = 0;i < top;i ++) //偶数^1 相当加1 奇数^1相当减1 当正向边 = 0&&路径不合适时，正加负减
{ //偶数是正向边，奇数是负向边，边从0开始
edge[stack[i]].cap -= min;
edge[stack[i]^1].cap += min;
} //将增广路中的所有边修改
res += min;
top = loc;
u = edge[stack[top]].frm; //当前结点修改为最小边的起点
}
for (i = cur[u];i != -1;cur[u] = i = edge[i].next) //找到当前结点对应的下一条边
if (edge[i].cap != 0&&dep[u] + 1 == dep[edge[i].to])//不满足条件时，修改cur值（去掉不合适的占）eg：1-->2 1-->3 1-->4 有边 但只有
break; // 1-->4 这条边满足条件 就把1到2、3的边给去掉
if (cur[u] != -1) //当前结点的下一条边存在
{
stack[top ++] = cur[u]; //把该边放入栈中
u = edge[cur[u]].to; //再从下个点开始找
}
else
{
if (top == 0) //当前结点无未遍历的下一条边且栈空，DFS找不到下一条增广路
break;
dep[u] = -1; //当前结点不在增广路中，剔除该点
u = edge[stack[--top]].frm; //退栈 回朔，继续查找
}
}
}
return res;
}
int in[VM],out[VM];
int abs(int qa)
{
if(qa>0) return qa;
return -qa;
}
int main()
{
int T,n,m;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ep=0;
memset (head,-1,sizeof(head));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(u == v)
continue;
out[u]++;
in[v]++;
if(!d)
{
addedge(u,v,1);
}
}
int flag=0;
int sum=0;
for(int i=1;i<=n;i++)
{
if(abs(in[i]-out[i])%2 == 1)
{
flag=1;
break;
}
if(in[i]<out[i])
{
addedge(0,i,(out[i]-in[i])/2);
sum += (out[i]-in[i])/2;
}
else
{
addedge(i,n+1,(in[i]-out[i])/2);
}
}
if(flag)
{
printf("impossible\n");
continue;
}
int ans = dinic(0,n+1);
if(sum == ans)
printf("possible\n");
else
printf("impossible\n");
}
return 0;
}
#include <stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 210
#define INFINITY 1000000000
struct edge
{
int cap;
int flow;
int ver;
edge *next;
edge *rev;
};
edge edges[2500];
edge *link[MAX+1];
int dist[MAX +1];
int h[MAX + 1];
int in[MAX+1];
int out[MAX+1];
int num;
int total_flow;
int min(int a, int b)
{
return a < b ? a : b;
};
void addedge(int start, int end, int c)
{
num++;
edges[num].ver = end;
edges[num].cap = c;
edges[num].next = link[start];
link[start] = edges + num;
num++;
edges[num].ver = start;
edges[num].cap = 0;
edges[num].next = link[end];
link[end] = edges + num;
link[start]->rev = link[end];
link[end]->rev = link[start];
}
void rev_bfs(int n, int src, int des)
{
int q[MAX + 1];
int head = 0;
int tail = 0;
for(int i = 1; i <= n; i++)
{
dist[i] = MAX;
h[i] = 0;
}
q[tail++] = des;
dist[des] = 0;
h[0] =补充：软件开发 , C++ ,
