频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 1422 最小路径覆盖
2012-08-24 14:31:58           
收藏   我要投稿

题意:一个地图上有n个小镇,以及连接着其中两个小镇的有向边,而且这些边无法形成回路。现在选择一些小镇空降士兵(1个小镇最多1个士兵),士兵能沿着边走到尽头,问最少空降几个士兵,能遍历完所有的小镇。


思路:匈牙利算法求最小路径覆盖:在一个有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联;(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次);解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个:X结点集中的i和Y结点集中的i',如果有边i->j,则在二分图中引入边i->j',设二分图最大匹配为m,则结果就是n-m

 

代码:

[cpp]
<span style="font-family:KaiTi_GB2312;font-size:18px;">#include<iostream> 
using namespace std; 
const int maxn=125; 
int map[maxn][maxn],visit[maxn],match[maxn]; 
int n; 
bool dfs(int v) 

     int i; 
     for(i=1;i<=n;i++) 
     { 
       if(map[v][i]&&!visit[i]) 
       { 
          visit[i]=1; 
          if(match[i]==-1||dfs(match[i])) 
          { 
            match[i]=v; 
            return true; 
          } 
       } 
     } 
     return false; 

             
int hungry() 

    int i,ans=0; 
    memset(match,-1,sizeof(match)); 
    for(i=1;i<=n;i++) 
    { 
       memset(visit,0,sizeof(visit)); 
       if(dfs(i)) ans++; 
    } 
    return ans; 

        
     
int main() 

    int i,t,j,a,b,ans,m; 
    scanf("%d",&t); 
    while(t--) www.2cto.com
    { 
      scanf("%d%d",&n,&m); 
      memset(map,0,sizeof(map)); 
      for(i=0;i<m;i++) 
      { 
        scanf("%d%d",&a,&b); 
        map[a][b]=1; 
      } 
      ans=n-hungry(); 
      printf("%d%\n",ans); 
    } 
    return 0; 

       
</span> 

点击复制链接 与好友分享!回本站首页
相关TAG标签 路径
上一篇: hdu 1695 综合数论 欧拉函数 分解质因子 容斥原理 打印素数表 帅呆了的一个题目 详解
下一篇:直接插入排序Linux下c 实现
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站