程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10735 混合圖的歐拉回路+輸出路徑

UVA 10735 混合圖的歐拉回路+輸出路徑

編輯：C++入門知識

UVA 10735 混合圖的歐拉回路+輸出路徑

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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(frontin[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;
}