把矩阵的的每一行当作一个顶点，每一列当作一个顶点，共两组顶点。如果点(i,j)有一个障碍，就是i行和j列有交点，也就是点i和点j有一条边，用最少的点覆盖所有的边，就是结果，也就是最小点覆盖，最小点覆盖数 = 最大匹配数
#include <cstdio>#include <cstring>const int MAXN = 510;int N,K;int grid[MAXN][MAXN];int linker[MAXN];bool vis[MAXN];bool dfs(int u){ for(int v = 1; v <= N; ++v) { if(!vis[v] && grid[u][v]) { vis[v] = true; if(!linker[v] || dfs(linker[v]) ) { linker[v] = u; return true; } } } return false;}int hungary(){ int res = 0; memset(linker,0,sizeof(linker)); for(int i = 1; i <= N; ++i) { memset(vis,false,sizeof(vis)); if(dfs(i)) ++res; } return res;}int main(){ int a,b; while(scanf("%d %d",&N,&K) != EOF) { memset(grid,0,sizeof(grid)); for(int i = 0; i < K; ++i) { scanf("%d %d",&a,&b); grid[a][b] = 1; } PRintf("%d/n",hungary()); } return 0;}新闻热点
疑难解答
