注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj2594 Treasure Exploration 二分匹配之最小路径覆盖+传递闭包  

2011-02-12 15:52:23|  分类: 图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2594

太经典了,最小路径覆盖之变形!如果题目中有暗示此图无环且路径是单向的话,必然是最小路径覆盖无疑!
这个题的题目意思和那个伞兵题差不多,但是伞兵走过的路径是可以交叉的,这样我们先做一个传递闭包,然后再连边做最小路径覆盖即可。

Source Code

Problem: 2594 User: 541780774
Memory: 652K Time: 1110MS
Language: G++ Result: Accepted

Source Code
#include<stdio.h>   #include<stdlib.h>   #include<string.h>      int nx, ny;             // X的點數目、Y的點數目    int mx[501], my[501];   // X各點的配對對象、Y各點的配對對象    bool vy[501];           // 紀錄Graph Traversal拜訪過的點    bool adj[501][501];     // 精簡過的adjacency matrix       // 以DFS建立一棵交錯樹    bool DFS(int x)    {        for (int y=0; y<ny; ++y)            if (adj[x][y] && !vy[y])            {                vy[y] = true;                   // 找到擴充路徑                  if (my[y] == -1 || DFS(my[y]))                {                   mx[x] = y; my[y] = x;                   return true;                   }            }        return false;    }       int bipartite_matching()    {        // 全部的點初始化為未匹配點。        memset(mx, -1, sizeof(mx));           memset(my, -1, sizeof(my));           // 依序把X中的每一個點作為擴充路徑的端點,        // 並嘗試尋找擴充路徑。        int c = 0;        for (int x=0; x<nx; ++x)   //     if (mx[x] == -1)    // x為未匹配點,這行可精簡。            {                // 開始Graph Traversal                memset(vy, false, sizeof(vy));                if (DFS(x)) c++;            }        return c;    }   void Floyd(int n)   {           int i,j,k;           for(k=0;k<n;k++)           for(i=0;i<n;i++)           for(j=0;j<n;j++)           {              if(i!=j&&adj[i][k]&&adj[k][j])              adj[i][j]=1;           }       }              main()   {            int i,a,b,n,m;            while(scanf("%d%d",&n,&m),n!=0||m!=0)            {               memset(adj, 0, sizeof(adj));                for(i=0;i<m;i++)               {                scanf("%d%d",&a,&b);                adj[a-1][b-1]=1;               }               Floyd(n);               nx=ny=n;               printf("%d\n",n-bipartite_matching());            }            system("pause");   }        
  评论这张
 
阅读(178)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018