把矩陣的的每一行當作一個頂點，每一列當作一個頂點，共兩組頂點。如果點(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; }新聞熱點
疑難解答
