独立博客: 哲学与程序

哲学与程序

混合图欧拉路例题 ZOJ1992

本文转载至哲学与程序博客:http://zhexue.sinaapp.com/?p=105

题目来源:ZOJ1992

对于一个混合图,即有有向边又有无向边的图,判断是否存在一条欧拉回路。
解法(转):混合图欧拉回路用的是网络流。把该图的无向边随便定向,计算每个点的入度和出度。如果有某个点出入度之差为奇数,那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度,也就是总度数为偶数,存在奇数度点必不能有欧拉回路。现在每个点入度和出度之差均为偶数。将这个偶数除以2,得x。即是说,对于每一个点,只要将x条边反向(入>出就是变入,出>入就是变出),就能保证出 = 入。如果每个点都是出 = 入,那么很明显,该图就存在欧拉回路。现在的问题就变成了:该改变哪些边,可以让每个点出 = 入?构造网络流模型。有向边不能改变方向,直接删掉。开始已定向的无向边,定的是什么向,就把网络构建成什么样,边长容量上限1。另新建s和t。对于入 > 出的点u,连接边(u, t)、容量为x,对于出 > 入的点v,连接边(s, v),容量为x(注意对不同的点x不同。当初由于不小心,在这里错了好几次)。之后,察看是否有满流的分配。有就是能有欧拉回路,没有就是没有。查看流值分配,将所有流量非 0(上限是1,流值不是0就是1)的边反向,就能得到每点入度 = 出度的欧拉图。由于是满流,所以每个入 > 出的点,都有x条边进来,将这些进来的边反向,OK,入 = 出了。对于出 > 入的点亦然。那么,没和s、t连接的点怎么办?和s连接的条件是出 > 入,和t连接的条件是入 > 出,那么这个既没和s也没和t连接的点,自然早在开始就已经满足入 = 出了。那么在网络流过程中,这些点属于“中间点”。我们知道中间点流量不允许有累积的,这样,进去多少就出来多少,反向之后,自然仍保持平衡。所以,就这样,混合图欧拉回路问题,解了。 

#include<stdio.h>
#include
<math.h>
#include
<algorithm>
#include
<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){ 
   
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j; 
   
if (source==sink) return inf; 
   
for (i=0;i<n;i++
       
for (j=0;j<n;flow[i][j++]=0); 
   
for (;;){ 
       
for (i=0;i<n;pre[i++]=0); 
        pre[t
=source]=source+1,d[t]=inf; 
       
for (p=q=0;p<=q&&!pre[sink];t=que[p++]) 
              
for (i=0;i<n;i++
               
if (!pre[i]&&(j=mat[t][i]-flow[t][i])) 
                     pre[que[q
++]=i]=t+1,d[i]=d[t]<j?d[t]:j; 
               
else if (!pre[i]&&(j=flow[i][t])) 
                 pre[que[q
++]=i]=-t-1,d[i]=d[t]<j?d[t]:j; 
       
if (!pre[sink]) break
       
for (i=sink;i!=source;) 
              
if (pre[i]>0
                flow[pre[i]
-1][i]+=d[sink],i=pre[i]-1
              
else 
                flow[i][
-pre[i]-1]-=d[sink],i=-pre[i]-1
    } 
   
for (i=0;i<n;i++)
       
if(mat[source][i] > flow[source][i])
           
return 0;
   
return 1
}
int main()
{
   
int T, degin[N],degout[N], n, m, x, y, z;
   
int flag;
    scanf(
"%d",&T);
   
while(T--){
        scanf(
"%d%d",&n,&m);
        memset(degin,
0,sizeof(degin));
        memset(degout,
0,sizeof(degout));
        memset(map,
0,sizeof(map));
       
for(int i = 0; i < m; i++){
            scanf(
"%d%d%d",&x,&y,&z);
            degout[x]
++;
            degin[y]
++;
           
if(!z)map[x][y]++;
        }
        flag
= 0;
       
for(int i = 1; i <= n && !flag; i++){
           
if((degin[i]+degout[i])%2)flag=1;
           
if(degin[i] > degout[i])
                map[i][n
+1] = (degin[i]-degout[i])/2;
           
else 
                map[
0][i] = (degout[i]-degin[i])/2;
        }
       
if(flag)
            printf(
"impossible\n");
       
else{
           
if(max_flow(n+2,map,0,n+1,flow))
                printf(
"possible\n");
           
else 
                printf(
"impossible\n");
        }
    }
   
return 0;
}

posted on 2011-12-25 21:28 哲学与程序 阅读(223) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序