poj 1637 混合欧拉回路 网络流 dinic 以及sap 算法 (二)
dge *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] = 1;
int p;
while(tail != head)
{
p = q[head++];
for(edge *e = link[p]; e; e = e->next)
{
if(dist[e->ver] != MAX || e->rev->cap == 0)
continue;
dist[e->ver] = dist[p] + 1;
h[dist[e->ver]]++;
q[tail++] = e->ver;
}
}
}
int sap(int n, int src, int des)
{
rev_bfs(n, src, des);
edge *cur_edges[MAX+1];
edge *rev_path[MAX+1];
total_flow = 0;
int i;
for(i = 1; i <= n ; i++)
cur_edges[i] = link[i];
int argu_flow = INFINITY;
int u = src;
while(dist[src] < n)
{
if(u == des)
{
for(i = src; i != des; i = cur_edges[i]->ver)
argu_flow = min(argu_flow, cur_edges[i]->cap);
for(i = src; i != des ; i = cur_edges[i]->ver)
{
cur_edges[i]->cap -= argu_flow;
cur_edges[i]->rev->cap += argu_flow;
cur_edges[i]->flow += argu_flow;
cur_edges[i]->rev->flow -= argu_flow;
}
total_flow += argu_flow;
u = src;
}
edge *e;
for(e = cur_edges[u]; e; e = e->next)
if(e->
cap > 0 && dist[u] == dist[e->ver] + 1)
break;
if(e)
{
cur_edges[u] = e;
rev_path[e->ver] = e->rev;
u = e->ver;
}
else
{
if(--h[dist[u]] == 0)
break;
cur_edges[u] = link[u];
int mini_dist = n;
for(edge *e = link[u]; e; e = e->next)
if(e->cap > 0)
mini_dist = min(mini_dist, dist[e->ver]);
dist[u] = mini_dist + 1;
h[dist[u]]++;
if(u != src)
u = rev_path[u]->ver;
}
}
return total_flow;
}
int main()
{
int T,m,n,src,des;
int u,v,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
num=0;
memset(link, 0, sizeof(link));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
src=n+1;
des=n+2;
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]