首页 > 代码库 > POJ3041 二分图最大匹配

POJ3041 二分图最大匹配

2024-07-10 16:05:42   220人阅读

问题：POJ3041

分析：

　　构造二分图：令A = B = { 1, 2, ... , n }, 分别代表行号集与列号集。假如第i行第j列有一颗行星，则连接Ai与Bj， 表示必须从Ai（即第i行），Bj（即第j列）中选择一个射击。最小射击数等价于覆盖所有边的最小点集S的大小。问题转化为最小顶点覆盖问题。

　　因为最小顶点覆盖=最大匹配数，故直接用匈牙利算法求解。

AC代码

 1 //Memory: 1260K        Time: 47MS 2 #include <iostream> 3 using namespace std; 4  5 int map[501][501]; 6 bool visit[10002]; 7 int match[10002]; 8 int n; 9 10 bool path(int start)11 {12     int i;13     14     for ( i = 1; i <= n; i++ )15     {16         if ( map[start][i] && !visit[i] ){17             visit[i] = true;18             if ( match[i] == -1 || path(match[i]) )19             {20                 match[i] = start;21                 return true;22             }23         }24     }25     return false;26 }27 28 int main()29 {30     int k,i;31     int x,y;32     int result;33     34     memset(match,-1,sizeof(match));35     memset(map,0,sizeof(map));36     cin >> n >> k;37     for ( i = 1; i <= k; i++ )38     {39         cin >> x >> y;40         map[x][y] = 1;41     }42     result = 0;43     for ( i = 1; i <= n; i++ )44     {45         memset(visit,false,sizeof(visit));46         if (path(i))47             result++;48     }49     cout << result << endl;50     return 0;51 }

 

　


联系
我们