程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10735 混合圖歐拉路徑的判定，方案輸出。

uva 10735 混合圖歐拉路徑的判定，方案輸出。

編輯：C++入門知識

Euler Circuit Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

Problem D
EulerCircuit
Input: standard input
Output: standard output
Time Limit: 2 seconds

AnEuler circuit is a graph traversal starting and ending at the same vertex andusing every edge exactly once. Finding an Euler circuit in an undirected ordirected graph is a fairly easy task, but what about graphs where some of theedges are directed and some undirected? An undirected edge can only be traveledin one direction. However, sometimes any choice of direction for the undirectededges may not yield an Euler circuit.

Givensuch a graph, determine whether an Euler circuit exists. If so, output such acircuit in the format specified below. You can assume that the underlyingundirected graph is connected.

Input

The first line in the inputcontains the number of test cases, at most 20.Each test case starts with a line containing two numbers, Vand E:the number of vertices (1 <= V <= 100) andedges (1<= E <= 500) in the graph. The verticesare numbered from 1 to V.Then follows Elines specifying the edges. Each such line will be in the format a b typewhere aand bare two integers specifying the endpoints of the edge. type will eitherbe the character 'U',if the edge is undirected, or 'D', if the edge is directed. Inthe latter case, the edge starts at a andends at b.

Output

If anEuler circuit exist, output an order in which the vertices can be traversed ona single line. The vertex numbers should be delimited with a single space, andthe start and end vertex should be included both at the beginning and the endof the sequence. Since most graphs have multiple solutions, any valid solutionwill be accepted. If no solution exist, output the line "No euler circuitexist". Output a blank line between each test case.

Sample Input Output for Sample Input

6 8

1 3 U

1 4 U

2 4 U

2 5 D

3 4 D

4 5 U

5 6 D

5 6 U

4 4

1 2 D

1 4 D

2 3 U

3 4 U

1 3 4 2 5 6 5 4 1

No euler circuit exist

歐拉回路的判定與前面的方法一樣，關鍵是路徑輸出問題，跑最大流之後，流量不為0的邊就是需要改變的邊，

忘記清空數組導致wa糾結了一下午。

代碼：

#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=20100;
const int maxm=1002000;
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]edge[S[i]].cap)
				   temp=edge[S[i]].cap,id=i;
		    for( i=0;idep[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],Head[maxn],tot,ans[maxn],top;
struct NODE{
	int next,to,vis;
}Edge[maxm];
void add(int u,int v){
	Edge[tot].to=v;
	Edge[tot].next=Head[u];
	Edge[tot].vis=0;
	Head[u]=tot++;
}
void dfs(int u){
	for(int i=Head[u];i!=-1;i=Edge[i].next){
		NODE &e=Edge[i];
		if(!e.vis){
			e.vis=1;
			dfs(e.to);
		}
	}
	ans[top++]=u;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,m,T;
	 scanf("%d",&T);
	 while(T--){
		 scanf("%d%d",&n,&m);
		 memset(head,-1,sizeof(head));tol=0;
		 memset(Head,-1,sizeof(Head));tot=0;
		 memset(in,0,sizeof(in));
		 memset(out,0,sizeof(out));
		 char op[10];
		 while(m--){
			 int u,v;
			 scanf("%d%d%s",&u,&v,op);
			 if(op[0]=='D')add(u,v);
			 else addedge(u,v,1);
			 out[u]++;in[v]++;
		 }
		 int flag=1,sum=0;
		 for(int i=1;i<=n;i++){
			 if((out[i]+in[i])%2){
				 flag=0;break;
			 }
			 if(out[i]>in[i])sum+=(out[i]-in[i])/2,addedge(0,i,(out[i]-in[i])/2);
			 else if(in[i]>out[i])addedge(i,n+1,(in[i]-out[i])/2);
		 }
		 if(!flag||sap(0,n+1,n+10)!=sum)puts("No euler circuit exist");
		 else{
			 top=0;
			 for(int i=1;i<=n;i++)
				 for(int j=head[i];j!=-1;j=edge[j].next){
					 int v=edge[j].to;
					 if(v>=1&&v<=n&&edge[j].cap>0)
						 add(i,v);
				 }
			 top=0;
			 dfs(1);
			 for (int i = top-1; i >= 0; i --) printf("%d%c",ans[i],i==0 ? '\n':' ');
		 }
		 if (T) puts("");
	 }
     return 0;
}