poj1637(混合图欧拉路 + Dinic)
题目大意：判定一个混合图是否是欧拉图。
过程：开始用EK算法来求解，用邻接矩阵存贮网络，但由于有重边的原因，一直是过不去，最后没办法，改用Dinic算法求解。
解题思路：无向边随意定向，将混合图转为有向图，利用网络流求解。
网络构造思路：在读入的时候遇到无向边的时候，将该无向边随意定向加入代建网络中，容量为1。读入完后，用每个点的入度减去出度得到x，若x为奇数，则肯定不存在欧拉回路。若所点的入度与初度之差（x）都为偶数，则用网络流解。
x>0，则在源点（s）与该点之间建立一条容量为 x/2 的边；
x<0，则在该点与汇点（t）之间建立一条容量为 -x/2 的边；
若该网络为满流网络（最大流 == 与源点相连的边容量之和），则该混合图是欧拉图，否则不是。
代码：
[cpp]
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 205
#define INF 0x7fffffff
struct Node
{
int v;
int cap;
int next;
}node[4050];
int in[MAXN],out[MAXN];
int level[MAXN],head[MAXN];
int que[MAXN];
int tot;
int min(int x,int y)
{
return x < y ? x : y ;
}
void init()
{
tot = 2;
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(head,-1,sizeof(head));
memset(node,'/0',sizeof(node));
}
void add(int s,int t,int cap)
{
node[tot].v=t;
node[tot].cap=cap;
node[tot].next = head[s];
head[s] = tot++;
node[tot].v=s;
node[tot].cap=0;
node[tot].next = head[t];
head[t]=tot++;
}
int BFS(int s,int t)
{
int head1=0,tail=0;
int u;
memset(level,-1,sizeof(level));
que[tail++]=s;
level[s]=0;
while(head1 != tail)
{
u = que[head1];
head1++;
int T=head[u];
while(T!=-1)
{
int v=node[T].v;
int cap=node[T].cap;
if(cap > 0 && level[v] == -1)
{
level[v] = level[u]+1;
que[tail++]=v;
}
T=node[T].next;
}
}
return level[t] != -1;
}
int DFS(int s,int mint,int t)
{
int temp;
if(s == t)
return mint;
int T = head[s];
while(T!=-1)
{
int v=node[T].v;
int cap=node[T].cap;
if(cap > 0 && level[v] == level[s]+1 && (temp = DFS(v,min(cap,mint),t))>0)
{
node[T].cap -= temp;
node[T^1].cap += temp;
return temp;
}
T=node[T].next;
}
return 0;
}
int dinic(int s,int t)
{
int res=0;
while(BFS(s,t))
{
while(1)
{
int a = DFS(s,INF,t);
if(a == 0)
break;
res += a;
}
}
return res;
}
int main()
{
int T,n,m;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
if(u == v)
continue;
out[u]++;
in[v]++;
if(!d)
{
add(u,v,1);
}
}
int flag=0;
int sum=0;
for(int i=1;i<=n;i++)
{
if(abs(in[i]-out[i])%2 == 1)
&nb
补充：软件开发 , C++ ,
