首页 > 代码库 > poj 1422 Air Raid （最小路径覆盖）

poj 1422 Air Raid （最小路径覆盖）

2024-07-25 20:26:37   219人阅读

链接：poj 1422

题意：有n个点和m条有向边，现在要在点上放一些伞兵，伞兵可以沿着图走，

直到不能走为止，每条边有且仅有一个伞兵走过，问最少放多少个伞兵

思路：求的最小路径覆盖，用二分图来做
对于这样的一个有向图做最小路径覆盖，首先建图
然后每一条有向边对应左边的点指向右边的点
这样建好图之后求最大匹配数
最小路径覆盖=点数-最大匹配数

[cpp] view plaincopyprint?
  1. #include<stdio.h>  
  2. #include<string.h>  
  3. int n,edge[150][150],link[150],used[150];  
  4. int dfs(int pos)  
  5. {  
  6.     int i;  
  7.     for(i=1;i<=n;i++)  
  8.         if(edge[pos][i]&&!used[i]){  
  9.             used[i]=1;  
  10.             if(link[i]==-1||dfs(link[i])){  
  11.                 link[i]=pos;  
  12.                 return 1;  
  13.             }  
  14.         }  
  15.     return 0;  
  16. }  
  17. int main()  
  18. {  
  19.     int T,i,m,a,b,s;  
  20.     scanf("%d",&T);  
  21.     while(T--){  
  22.         scanf("%d%d",&n,&m);  
  23.         memset(edge,0,sizeof(edge));  
  24.         for(i=1;i<=m;i++){  
  25.             scanf("%d%d",&a,&b);  
  26.             edge[a][b]=1;  
  27.         }  
  28.         memset(link,-1,sizeof(link));  
  29.         s=0;  
  30.         for(i=1;i<=n;i++){  
  31.             memset(used,0,sizeof(used));  
  32.             s+=dfs(i);  
  33.         }  
  34.         printf("%d\n",n-s);  
  35.     }  
  36.     return 0;  
  37. }  

poj 1422 Air Raid （最小路径覆盖）


联系
我们