首页 > 代码库 > UVA 10735 混合图的欧拉回路+输出路径
UVA 10735 混合图的欧拉回路+输出路径
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<set> #include<map> #include<queue> #include<vector> #include<string> #define eps 1e-12 #define INF 0x7fffffff #define maxn 22222 using namespace std; int n,m; int en; int st,ed; int dis[maxn] ; int que[999999]; int cur[maxn],head2[maxn],en2; struct edge { int to,c,next; }e2[999999]; edge e[999999]; int head[maxn],in[maxn],out[maxn]; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } void add(int a,int b) { // printf("%d->%d\n",a,b); e2[en2].to=b; e2[en2].next=head2[a]; head2[a]=en2++; } int bfs() { memset(dis,-1,sizeof(dis)); dis[st]=0; int front=0,rear=0; que[rear++]=st; while(front<rear) { int j=que[front++]; for(int k=head[j];k!=-1;k=e[k].next) { int i=e[k].to; if(dis[i]==-1&&e[k].c) { dis[i] = dis[j]+ 1 ; que[rear++]=i; if(i==ed) return true; } } } return false; } int dfs(int x,int mx) { if(x==ed || mx==0) return mx; int f,flow=0; for(int& i=cur[x];i!=-1;i=e[i].next) { if(dis[x]+1==dis[e[i].to] && (f=dfs(e[i].to,min(mx,e[i].c)))) { e[i].c-=f; e[i^1].c+=f; flow+=f; mx-=f; if(!mx)break; } } return flow; } int ans[maxn<<2]; int top; bool vis[maxn<<2]; void dfs2(int now) { for(int i=head2[now];~i;i=e2[i].next) { if(!vis[i]) { vis[i]=true; dfs2(e2[i].to); } } ans[top++]=now; } void init() { top=en2=en=0; st=0; ed=n+1; memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); } int dinic() { int tmp=0; int maxflow=0; while(bfs()) { for(int i=st;i<=ed;i++) cur[i]=head[i]; while(tmp=dfs(st,INF)) maxflow+=tmp; } return maxflow; } int f=0; void build() { int x,y,z,sum=0; char str[10]; for(int i=1;i<=m;i++) { scanf("%d%d%s",&x,&y,str); if(str[0]=='U') { add(x,y,1); } else { add(x,y); } in[y]++; out[x]++; } if(f) puts(""); f=1; for(int i=1;i<=n;i++) { if(abs(out[i]-in[i])&1) {puts("No euler circuit exist");return;} if(out[i]>in[i]) { add(st,i,(out[i]-in[i])/2),sum+=(out[i]-in[i])/2; } else { add(i,ed,(in[i]-out[i])/2); } } if(sum==dinic()) { for(int i=1;i<=n;i++) for(int j=head[i];~j;j=e[j].next) { if(e[j].to>=1&&e[j].to<=n) { if(e[j].c)add(i,e[j].to); } } dfs2(1); printf("%d",ans[top-1]); for(int i=top-2;i>=0;i--) printf(" %d",ans[i]); puts(""); } else puts("No euler circuit exist"); } int main() { int cas; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); init(); build(); } return 0; }
UVA 10735 混合图的欧拉回路+输出路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。