POJ 1637 混合图欧拉回路判定

Description

Input

Output

Sample Input

4
5 8
2 1 0
1 3 0
4 1 1
1 5 0
5 4 1
3 4 0
4 2 1
2 2 0
4 4
1 2 1
2 3 0
3 4 0
1 4 1
3 3
1 2 0
2 3 0
3 2 0
3 4
1 2 0
2 3 1
1 2 0
3 2 0

Sample Output

possible
impossible
impossible
possible

Source

只需要判断出度入度，然后就是建图跑最大流判断是否满流。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/26 10:45:50
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=20010;
const int maxm=1000000;
struct Edge{
	int next,to,cap;
	Edge(){};
	Edge(int _next,int _to,int _cap){
		next=_next;to=_to;cap=_cap;
	}
}edge[maxm];
int head[maxn],tol,dep[maxn],gap[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0,Q[maxn];
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int sap(int s,int t,int N){
	int res=0;bfs(s,t);
	int cur[maxn],S[maxn],top=0,u=s,i;
	memcpy(cur,head,sizeof(head));
	while(dep[s]<N){
		if(u==t){
			int temp=INF,id;
		    for( i=0;i<top;i++)
			   if(temp>edge[S[i]].cap)
				   temp=edge[S[i]].cap,id=i;
		    for( i=0;i<top;i++)
			      edge[S[i]].cap-=temp,edge[S[i]^1].cap+=temp;
		    res+=temp;top=id;u=edge[S[top]^1].to;
		}
		if(u!=t&&gap[dep[u]-1]==0)break;
		for( i=cur[u];i!=-1;i=edge[i].next)
			if(edge[i].cap&&dep[u]==dep[edge[i].to]+1)break;
		if(i!=-1)cur[u]=i,S[top++]=i,u=edge[i].to;
		else{
			int MIN=N;
			for( i=head[u];i!=-1;i=edge[i].next)
				if(edge[i].cap&&MIN>dep[edge[i].to])
					MIN=dep[edge[i].to],cur[u]=i;
			--gap[dep[u]];++gap[dep[u]=MIN+1];
			if(u!=s)u=edge[S[--top]^1].to;
		}
	}
	return res;
}
int in[maxn],out[maxn];

int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int T,t;
	 scanf("%d",&T);
     for(t=1;t<=T;t++){
		 int n,m;
		 scanf("%d%d",&n,&m);
		 memset(in,0,sizeof(in));
		 memset(out,0,sizeof(out));
		 memset(head,-1,sizeof(head));tol=0;
		 int i,j,k;
		 while(m--){
			scanf("%d%d%d",&i,&j,&k);
			 out[i]++;in[j]++;
			 if(k==0)addedge(i,j,1);
		 }
		 int flag=1;
				int sum=0;
				for(int i=1;i<=n;i++){
					int ret=out[i]-in[i];
					if(ret>0)addedge(0,i,ret/2),sum+=ret/2;
					else if(ret<0)addedge(i,n+1,-ret/2);
					if((in[i]+out[i])%2){
						flag=0;break;
					}
				}
				if(!flag){
					puts("impossible");continue;
				}
				int ans=sap(0,n+1,n+10);
				if(ans==sum)puts("possible");
				else puts("impossible");
	 }
     return 0;
}

POJ 1637 混合图欧拉回路判定,布布扣,bubuko.com

POJ 1637 混合图欧拉回路判定

原文：http://blog.csdn.net/xianxingwuguan1/article/details/22161355