poj Antenna Placement(二分图的匹配)

是最小路径覆盖问题:最小路径覆盖=最小路径覆盖=|G|-最大匹配数 
#include
<stdio.h> #include<string.h> const int maxn = 40*10+10; int maps[45][15],g[maxn][maxn],linker[maxn],vis[maxn],uN,vN; int dfs(int u) { for(int v = 1; v <= vN; v++) if(!vis[v] && g[u][v]) { vis[v] = 1; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return 1; } } return 0; } int hungary() { int sum = 0; memset(linker,-1,sizeof(linker)); for(int u = 1; u <= uN; u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) sum++; } return sum; } int main() { int T,row,col; scanf("%d",&T); while(T--) { scanf("%d%d%*c", &row,&col); char c; int num = 0; memset(maps,0,sizeof(maps)); memset(g,0,sizeof(g)); for(int i = 1; i <= row; i++) { for(int j = 1; j <= col; j++) { scanf("%c", &c); if(c == ‘*‘) maps[i][j] = ++num; } getchar(); } uN = vN = num; for(int i = 1; i <= row; i++) { for(int j = 1; j <= col; j++) { if(maps[i][j]) { if(maps[i][j+1]) g[maps[i][j]][maps[i][j+1]] = 1; if(maps[i][j-1]) g[maps[i][j]][maps[i][j-1]] = 1; if(maps[i+1][j]) g[maps[i][j]][maps[i+1][j]] = 1; if(maps[i-1][j]) g[maps[i][j]][maps[i-1][j]] = 1; } } } printf("%d\n", num-hungary()/2); } return 0; }

poj Antenna Placement(二分图的匹配)

上一篇:为什么云计算是最具颠覆性的力量?


下一篇:Selector中的各种状态详解