把矩陣的的每一行當(dāng)作一個(gè)頂點(diǎn)，每一列當(dāng)作一個(gè)頂點(diǎn)，共兩組頂點(diǎn)。如果點(diǎn)(i,j)有一個(gè)障礙，就是i行和j列有交點(diǎn)，也就是點(diǎn)i和點(diǎn)j有一條邊，用最少的點(diǎn)覆蓋所有的邊，就是結(jié)果，也就是最小點(diǎn)覆蓋，最小點(diǎn)覆蓋數(shù) = 最大匹配數(shù)
#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; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
