(step6.3.4)hdu 1151(Air Raid——最小路径覆盖)

时间:2022-08-31 12:17:56

题意:

    一个镇里所有的路都是单向路且不会组成回路。

派一些伞兵去那个镇里,要到达所有的路口,有一些或者没有伞兵可以不去那些路口,只要其他人能完成这个任务。每个在一个路口着陆了的伞兵可以沿着街去到其他路口。我们的任务是求出去执行任务的伞兵最少可以是多少个。

思路:

这个题就是个最小路径覆盖问题。

路径覆盖的定义是:在有向图中找一些路径,使之覆盖了图中的所有顶点,就是任意一个顶点都跟那些路径中的某一条相关联,且任何一个顶点有且只有一条路径与之关联,一个单独的顶点是一条路径.最小路径覆盖就是最少的路径覆盖数。

(step6.3.4)hdu 1151(Air Raid——最小路径覆盖)
 如上图,最小路径覆盖的那条路应该是{e1,e4,e5,e6,e7},最小路径覆盖就是1。
 
    有定理:   最小路径覆盖  =  图的顶点数  –  最大匹配数。
 
    其实那个最大匹配数并   非 原图 的最大匹配数,而是最小路径覆盖的边的条数,是把图中每个点拆成两个点,再算出来的最大匹配数。很容易证明两者是相同的。
 
     可是有一点不明白,为什么原图用匈牙利算法算出最大匹配数,与图的顶点数想减,最后求出的最小路径覆盖是对的呢,而不需要用拆点后的图来算呢?
 
-----原来我建的邻接表它本身就拆点了,所以不矛盾。

--------------------------以上为摘抄别的大牛的

代码如下:
/*
* 1151_1.cpp
*
* Created on: 2013年8月31日
* Author: Administrator
*/
#include <iostream> using namespace std; const int maxn = 1001;
int map[maxn][maxn];
int link[maxn];
bool useif[maxn];
int n; int can(int t){
int i;
for(i = 1 ; i<= n ; ++i){
if(useif[i] == 0 && map[t][i]){
useif[i] = 1;
if(link[i] == - 1 || can(link[i])){
link[i] = t;
return 1;
}
}
} return 0;
} int max_match(){
int i;
int num = 0;
memset(link,-1,sizeof(link));
for(i = 1 ; i <= n ; ++i){
memset(useif,0,sizeof(useif));
if(can(i)){
num++;
}
}
return num;
} int main(){
int t;
scanf("%d",&t);
while(t--){
int k;
memset(map,0,sizeof(map));
scanf("%d%d",&n,&k); int i;
for(i = 1 ; i <= k ; ++i){
int a,b;
scanf("%d%d",&a,&b);
map[a][b] = 1;
} printf("%d\n",n - max_match()); }
}

(step6.3.4)hdu 1151(Air Raid——最小路径覆盖)的更多相关文章

  1. hdu 1151 Air Raid 最小路径覆盖

    题意:一个城镇有n个路口,m条路.每条路单向,且路无环.现在派遣伞兵去巡逻所有路口,伞兵只能沿着路走,且每个伞兵经过的路口不重合.求最少派遣的伞兵数量. 建图之后的就转化成邮箱无环图的最小路径覆盖问题 ...

  2. &lpar;hdu step 6&period;3&period;3&rpar;Air Raid&lpar;最小路径覆盖:求用最少边把全部的顶点都覆盖&rpar;

    题目: Air Raid Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total ...

  3. 【网络流24题----03】Air Raid最小路径覆盖

    Air Raid Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Su ...

  4. HDU1151 Air Raid —— 最小路径覆盖

    题目链接:https://vjudge.net/problem/HDU-1151 Air Raid Time Limit: 2000/1000 MS (Java/Others)    Memory L ...

  5. POJ 1422 Air Raid &lpar;最小路径覆盖&rpar;

    题意 给定一个有向图,在这个图上的某些点上放伞兵,可以使伞兵可以走到图上所有的点.且每个点只被一个伞兵走一次.问至少放多少伞兵. 思路 裸的最小路径覆盖. °最小路径覆盖 [路径覆盖]在一个有向图G( ...

  6. Air Raid&lpar;最小路径覆盖&rpar;

    Air Raid Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 7511   Accepted: 4471 Descript ...

  7. hdu 1151 Air Raid&lpar;二分图最小路径覆盖)

    http://acm.hdu.edu.cn/showproblem.php?pid=1151 Air Raid Time Limit: 1000MS   Memory Limit: 10000K To ...

  8. hdu - 1151 Air Raid&lpar;有向无环图的最小路径覆盖&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=1151 在一个城市里有n个地点和k条道路,道路都是单向的,并且不存在环.(DAG) 现在伞兵需要去n个地点视察,伞 ...

  9. HDU 1151 Air Raid(最小路径覆盖)

    题目大意: 有n个城市,m条道路,城市的道路是单向.  现在我们的伞兵要降落在城市里,然后我门的伞兵要搜索所有道路.问我们最少占领多少个城市就可以搜索所有的道路了. 我们可以沿着道路向前走到达另一个城 ...

随机推荐

  1. 运用node的文件系统模块批量修改文件名

      如果我们需要大批量修改一个文件中的名称,比如,删除文件名中的副本时,就可以借助node的文件系统模块,快捷快速的完成. 首先建立一个js文件(changeName.js),代码如下: // 引入f ...

  2. 解决在CentOS6&period;5下安装OpenStack(Icehouse版本 )出现的glance服务无法正常工作的问题

    最近一直在用Juno版本,因为项目需要,今天在虚拟机里安装了Icehouse版,其中glance组件在执行安装的过程后,出现启动失败的现象,幸好以前排查过此类错误,遂记录如下: 在官方文档(Iceho ...

  3. Listview的点击事件

    上篇文章总结了如何自定义listview的显示内容,然而listview不能只是提供显示功能,还必须能够点击它显示一些东西: listView.setOnItemClickListener(new O ...

  4. JavaScript中对于闭包的理解

    1.什么是闭包? 闭包,官方对闭包的解释是:一个拥有很多变量和绑定了这些变量的环境的表达式(通常是一个函数),因而这些变量也是该表达式的一部分. 闭包的特点: (1).作为一个函数变量的一个引用,当函 ...

  5. linux&sol;windows系统oracle数据库简单冷备同步

    linux/windows系统oracle数据库简单冷备同步 我们有一个财务系统比较看重财务数据的安全性,同时我们拥有两套系统,一个生产环境(linux),一个应急备份环境(windows).备份环境 ...

  6. Image控件播放 GIF文件

    uses Vcl.Imaging.GIFImg;procedure TForm1.Button2Click(Sender: TObject);begin    Image1.Picture.LoadF ...

  7. CSS筛选器简单实例1

    1.通配符 <!--筛选器---通配符实例--> <!--支持IE7+ --> <style type="text/css"> *.all { ...

  8. 如何获取DOM中当前获取焦点的元素

    <script type="text/javascript"> function msg(e) // e = event { var target; //initial ...

  9. Nginx反向代理WebSocket

    http { upstream websocket { server 192.168.1.1:8010; } server { listen 8020; location / { proxy_pass ...

  10. Alpha阶段项目展示博客

    烫烫烫烫烫(hotcode5)团队 1. 团队成员的简介和个人博客地址 刘畅 博客园ID:森高Slontia 身份:PM 个人介绍: 弹丸粉 || 小说创作爱好者 || 撸猫狂魔(x || 生命的价值 ...