锐客网

  1. 首页 > it技术 > >

poj|poj1422 - Air Raid

想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处：http://blog.csdn.net/wangjian8006
【poj|poj1422 - Air Raid】题目大意：有n个点和m条有向边，现在要在点上放一些伞兵，然后伞兵沿着图走，直到不能走为止
每条边只能是一个伞兵走过，问最少放多少个伞兵

解题思路：这是一个很明显的最小路径覆盖，用二分图来做
对于这样的一个有向图做最小路径覆盖，首先建图
先拆点，将每个点分为两个点，左边是1到n个点，右边是1-n个点
然后每一条有向边对应左边的点指向右边的点
这样建好图之后求最大匹配数
因为最小路径覆盖=点数-最大匹配数

/* Memory 232K Time0MS */ #include using namespace std; #define MAXV 130int n,m; //交叉路口和街道的个数 int map[MAXV][MAXV]; int link[MAXV],use[MAXV]; bool dfs(int x){ int i,j; for(i=1; i<=n; i++){ if(map[x][i] && !use[i] ){//拆点注意i不能等于x，否则就自己和自己匹配了 j=link[i]; use[i]=1; link[i]=x; if(j==-1 || dfs(j)) return true; link[i]=j; } } return false; }int hungary(){ int num=0; int i; memset(link,-1,sizeof(link)); for(i=1; i<=n; i++){ memset(use,0,sizeof(use)); if(dfs(i)) num++; } return n-num; }int main(){ int Case; int a,b,i; scanf("%d",&Case); while(Case--){ scanf("%d%d",&n,&m); memset(map,0,sizeof(map)); for(i=0; i



    推荐阅读


    上一篇：Springmvc与Mongo GridFs 实现文件的上传和获取

    下一篇：Spark|Spark Streaming状态操作: updateStateByKey、mapWithState、基于window的状态操作