混合图的欧拉回路，用网络流做。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-21
DESCRIPTION:
网络流 乱做
http://acm.pku.edu.cn/JudgeOnline/problem?id=1637
*/
#include <stdio.h>
#include <string.h>
const int oo=(~0u)>>1;
const int MAXV=1102;
const int MAXE=6200;
typedef struct struct_edge* edge;
struct struct_edge{int v,c;edge n,b;};
struct_edge pool[MAXE];
edge top;
int S,T,V;
edge adj[MAXV];
int d[MAXV];
int q[MAXV];
int head,tail;
void add_edge(int u,int v,int c)
{
top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;
top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;
adj[u]->b=adj[v],adj[v]->b=adj[u];
}
bool relabel()
{
for (int i=0;i<V;d[i++]=oo) ;
d[q[head=tail=0]=T]=0;
while (head<=tail)
{
int u=q[head++];
for (edge i=adj[u];i;i=i->n)
if (i->b->c&&d[i->v]==oo)
d[q[++tail]=i->v]=d[u]+1;
if (d[S]!=oo) return true;
}
return false;
}
int augment(int u,int e)
{
if (u==T) return e;
int f=0;
for (edge i=adj[u];i&&e;i=i->n)
if (i->c&&d[u]==d[i->v]+1)
if (int df=augment(i->v,e<i->c?e:i->c))
i->c-=df,i->b->c+=df,e-=df,f+=df;
return f;
}
int dinic()
{
int f=0;
while (relabel()) f+=augment(S,oo);
return f;
}
const int SIZE=1000;
int n,m,s,a[SIZE],b[SIZE],c[SIZE];
int degree[SIZE];
int main()
{
scanf(“%d”,&n);
for (int t=0;t<n;t++)
{
scanf(“%d%d”,&m,&s);
memset(degree,0,sizeof(degree));
for (int i=0;i<s;i++)
scanf(“%d%d%d”,a+i,b+i,c+i),
degree[a[i]]++,degree[b[i]]–;
top=pool;
memset(adj,0,sizeof(adj));
S=0,T=m+1,V=m+2;
int total=0;
bool no_solution=false;
for (int i=1;i<=m;i++)
{
if (degree[i]&1) no_solution=true;
if (degree[i]>0) add_edge(S,i,degree[i]>>1),total+=degree[i]>>1;
else add_edge(i,T,(-degree[i])>>1);
}
for (int i=0;i<s;i++)
if (!c[i]) add_edge(a[i],b[i],1);
if (no_solution||dinic()!=total) printf(“im”);
printf(“possible\n”);
}
}