beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

混合图欧拉回路

Posted on 2010-10-14 20:07 成幸毅 阅读(455) 评论(0)  编辑 收藏 引用
   给出一个N个点和M条边的混合图,求出它的一条欧拉回路,如果没有,输出无解信息。
   无向边只能经过一次,所以不能把它拆成两条方向相反的有向边,而只能给每条无向边定向。有向图欧拉回路的有条性质是:当且仅当,图连通,并且每个节点的入度等于出度!!这题可以先给每条无向边定向,随意定。这样,每个节点现在大有可能出度不等于入度。如果一个点入度大于出度,那么让这s与这点相连,边容量为(出度-入度)/2;代表这个节点经过两次修改后能让出度等于入度。反之,连t节点。道理一样。如果是满流,那就对了,欧拉图。
  
int main() {
   
int cas;
   scanf(
"%d",&cas);
   
while(cas--{
      memset(degree,
0,sizeof(degree));
      memset(head,
-1,sizeof(head));
      sps 
= 0;
      
int sum = 0;
      scanf(
"%d%d",&n,&m);
      
for(int i = 0; i < m; i++{
         scanf(
"%d%d%d",&vex1[i],&vex2[i],&dir[i]);
         degree[vex1[i]]
++;
         degree[vex2[i]]
--;
      }

        
int i;
       
for( i = 1; i <= n; i++{
           
if(abs(degree[i])&1)
              
break;
       }

       
if(i <= n)  {
            printf(
"impossible\n"); continue;
       }


      s 
= 0,t = n+1;
      NN 
= t+1;
      
for(int i = 0; i < m; i++{
         
if(!dir[i] && vex1[i] != vex2[i])
            addedge(vex1[i],vex2[i],
1);
      }

      
for(int i = 1; i <= n;i++{
         
if(degree[i] > 0{
            addedge(s,i,(degree[i])
/2);
            sum 
+= degree[i]/2;
         }

         
         
else if(degree[i] < 0{
            addedge(i,t,
-degree[i]/2);
         }

      }

         
if(maxFlow(s,t) == sum) {
            printf(
"possible\n");
         }

         
else 
            printf(
"impossible\n");
   }

  
// system("pause");
   return 0;
}


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