• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            獨立博客: 哲學與程序

            哲學與程序

            混合圖歐拉路(判斷)

            問題:對于一個混合圖,即有有向邊又有無向邊的圖,判斷是否存在一條歐拉回路。
            解法(轉(zhuǎn)):混合圖歐拉回路用的是網(wǎng)絡(luò)流。把該圖的無向邊隨便定向,計算每個點的入度和出度。如果有某個點出入度之差為奇數(shù),那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度,也就是總度數(shù)為偶數(shù),存在奇數(shù)度點必不能有歐拉回路。現(xiàn)在每個點入度和出度之差均為偶數(shù)。將這個偶數(shù)除以2,得x。即是說,對于每一個點,只要將x條邊反向(入>出就是變?nèi)?,?gt;入就是變出),就能保證出 = 入。如果每個點都是出 = 入,那么很明顯,該圖就存在歐拉回路。現(xiàn)在的問題就變成了:該改變哪些邊,可以讓每個點出 = 入?構(gòu)造網(wǎng)絡(luò)流模型。有向邊不能改變方向,直接刪掉。開始已定向的無向邊,定的是什么向,就把網(wǎng)絡(luò)構(gòu)建成什么樣,邊長容量上限1。另新建s和t。對于入 > 出的點u,連接邊(u, t)、容量為x,對于出 > 入的點v,連接邊(s, v),容量為x(注意對不同的點x不同。當初由于不小心,在這里錯了好幾次)。之后,察看是否有滿流的分配。有就是能有歐拉回路,沒有就是沒有。查看流值分配,將所有流量非 0(上限是1,流值不是0就是1)的邊反向,就能得到每點入度 = 出度的歐拉圖。由于是滿流,所以每個入 > 出的點,都有x條邊進來,將這些進來的邊反向,OK,入 = 出了。對于出 > 入的點亦然。那么,沒和s、t連接的點怎么辦?和s連接的條件是出 > 入,和t連接的條件是入 > 出,那么這個既沒和s也沒和t連接的點,自然早在開始就已經(jīng)滿足入 = 出了。那么在網(wǎng)絡(luò)流過程中,這些點屬于“中間點”。我們知道中間點流量不允許有累積的,這樣,進去多少就出來多少,反向之后,自然仍保持平衡。所以,就這樣,混合圖歐拉回路問題,解了。
            ZOJ@1992
            // 2391682      2011-01-24 10:49:56        Accepted      1992      C++      90      508      redsea
            #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-01-24 10:51 哲學與程序 閱讀(369) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm

            導航

            公告

            歡迎訪問 http://zhexue.sinaapp.com

            常用鏈接

            隨筆分類(37)

            隨筆檔案(41)

            Algorithm

            最新隨筆

            搜索

            最新評論

            獨立博客: 哲學與程序
            99久久人人爽亚洲精品美女| 国产福利电影一区二区三区,免费久久久久久久精 | 亚洲色欲久久久久综合网| 久久性生大片免费观看性| 亚洲午夜久久久影院| 国产69精品久久久久9999| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 亚洲精品无码久久毛片| 久久水蜜桃亚洲av无码精品麻豆| 久久国产乱子精品免费女| 午夜福利91久久福利| 久久99精品国产99久久6男男| 久久久久国产精品三级网| 久久超碰97人人做人人爱| 日韩欧美亚洲国产精品字幕久久久 | 久久不见久久见免费视频7| 超级碰碰碰碰97久久久久| 国产精品成人99久久久久| 久久久久无码精品国产| 久久毛片一区二区| 久久综合久久鬼色| 18岁日韩内射颜射午夜久久成人| 99精品久久久久久久婷婷| 伊人久久大香线蕉精品不卡| 久久国产精品一区| 久久国产成人亚洲精品影院| 色综合久久中文综合网| 久久综合国产乱子伦精品免费| 青青久久精品国产免费看| 久久精品无码专区免费| 99久久精品国产毛片| 久久精品人人做人人爽电影| 国产精品久久网| 国产精品久久影院| 国产精品久久久久久久久久免费| 国产亚洲婷婷香蕉久久精品| 久久本道伊人久久| 久久久久九九精品影院| 亚洲国产精品综合久久网络| 亚洲国产成人精品无码久久久久久综合 | 人妻无码中文久久久久专区|