poj1637&&hdu1956 混合欧拉回图判断

欧拉路：经过所有路有且仅有1次，可以路过所有的点。

无向图: 图连通，所有点都是偶数度，或者只有两个点是奇数度。当所有点是偶数度时欧拉路起点可以是任意点；当有两个奇数度点时起点必须是奇数度点。

有向图: 图连通，所有点出度=入度，或者有一个点入度-出度=1，有一个点出度-入度=1。同样，当所有点出度=入度时任意点可作为起点；而后者必须以出度-入度=1的

点做起点，入度-出度=1的点做终点。

混合图

首先可以想到的是枚举欧拉路径的起点i和终点j，然后在图中添加边<j, i>，再求图中是否有欧拉回路即可。但是，该算法的时间复杂度达到了O(M * 最大流的时间)，需要优化。
前面已经说过，在将边变向的过程中任何点的D值的奇偶性都不会改变，而一个有向图有欧拉路径的充要条件是基图连通且有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），其余点的入度等于出度。这就说明，先把图中的无向边随便定向，然后求每个点的D值，若有且只有两个点的初始D值为奇数，其余的点初始D值都为偶数，则有可能存在欧拉路径（否则不可能存在）。进一步，检查这两个初始D值为奇数的点，设为点i和点j，若有D[i]>0且D[j]<0，则i作起点j作终点（否则若D[i]与D[j]同号则不存在欧拉路径），连边<j, i>，求是否存在欧拉环即可（将求出的欧拉环中删去边<j, i>即可）。这样只需求一次最大流。

欧拉回路：经过所有路有且仅有1次，可以路过所有的点，最后要回到起点。

无向图: 图连通，所有点都是偶数度。

有向图: 图连通，所有点出度=入度。

混合图: 构造网络流模型来进行判断，具体如下:

先对原图中的无向边随便定向，然后计算每个点的出度和入度，如果存在|出度-入度|为奇数的点，则

不存在欧拉回路(因为欧拉回路要求每个点出度=入度，而对无向图随便定向不影响点的 |出度-入度|

的奇偶性，所以如果存在这样的点，不论怎么样都不可能找到欧拉回路)；否则，对于每个点来说，

求出它的|出度-入度|/2，得到X。然后开始构造网络：原图中的无向边怎么定向，网络中就怎么连边，

容量为1；然后对于每个点,如果(出度-入度)大于0，就和源点连边，容量为X；如果(出度-入度)大于0，

就和汇点连边，容量为X；然后对这个网络求最大流，如果能够满流，则原图存在欧拉回路，否则不存

在。

#include<stdio.h>

#include<string.h>

#include<queue>

#define maxn 300

#define INF 99999999

using namespace std;

struct node

{

    int to;

    int v;

    int next;

    int flag;

}edge[*];

int s,t,pre[maxn],index,vis[maxn],in[maxn],out[maxn],sum,n;

int min(int x,int y)

{

    return x<y?x:y;

}

void add(int x,int y,int z)

{

    edge[index].to=y;

    edge[index].v=z;

    edge[index].flag=index+;

    edge[index].next=pre[x];

    pre[x]=index++;

    edge[index].to=x;

    edge[index].v=;

    edge[index].flag=index-;

    edge[index].next=pre[y];

    pre[y]=index++;

}

int dfs(int u,int low)

{

    int i;

    if(u==t)

        return low;

    for(i=pre[u];i!=-;i=edge[i].next)

    {

        if(vis[edge[i].to]==vis[u]+&&edge[i].v>)

        {

            int a=dfs(edge[i].to,min(low,edge[i].v));

            if(a<=)continue;

            edge[i].v-=a;

            edge[edge[i].flag].v+=a;

            return a;

        }

    }

    return ;

}

int BFS()

{

    int i;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(i=pre[t];i!=-;i=edge[i].next)

        {

            if(vis[edge[i].to]<&&edge[i].v>)

            {

                vis[edge[i].to]=vis[t]+;

                q.push(edge[i].to);

            }

        }

    }

    if(vis[t]>)

        return ;

    return ;

}

void init()

{

    int m,i;

    sum=;

    index=;

    memset(in,,sizeof(in));

    memset(out,,sizeof(out));

    memset(pre,-,sizeof(pre));

    scanf("%d%d",&n,&m);

    s=,t=n+;

    for(i=;i<m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        if(z==)add(x,y,);

        in[y]++;

        out[x]++;

    }

}

void slove()

{

    int i;

    int flag=;

    for(i=;i<=n;i++)

    {

        if((in[i]-out[i])%!=)

        {

            flag=;

            break;

        }

        else

        {

            if(out[i]>in[i])

            {

                add(,i,(out[i]-in[i])/);

                sum+=((out[i]-in[i])/);

            }

            else if(out[i]<in[i])

            {

                add(i,t,(in[i]-out[i])/);

            }

        }

    }

    if(flag)

    {

        printf("impossible\n");

    }

    else

    {

        int ans=;

        while(BFS())

        {

            while()

            {

                int a=dfs(,INF);

                if(!a)break;

                ans+=a;

            }

        }

        if(ans==sum)

            printf("possible\n");

        else printf("impossible\n");

    }

}

int main()

{

    int ft;

    scanf("%d",&ft);

    while(ft--)

    {

        init();

        slove();

    }

}

巴特西

poj1637&&hdu1956 混合欧拉回图判断

最新文章

热门文章