【POJ 3020】Antenna Placement
二分图的最大独立集问题 ‘o’表示间断点 要求把所有* 连接 每条路可连接一个或连续的两个* 最大匹配可以满足仅连接连续两个所能构成的最长路径 之后未被连接的点需要单独圈来套住 即n(总*数)-m(最大匹配)+m(最大匹配)/2 (由于建立的是双向路径 得到的最大匹配其实表示两两连接后连接的总点数)
代码如下:
;char Map[41][13];bool mp[555][555],vis[555];int tp,n,link[555];int dirx[] = { -1, 0, 1, 0};int diry[] = { 0, -1, 0, 1};int dir[4];bool can(int p){int i,j;for(i = 0; i < 4; ++i){if(p + dir[i] < 0 && p + dir[i] >= n) continue;j = p + dir[i];if(!vis[j] && mp[p][j]){vis[j] = true;if(link[j] == -1 || can(link[j])){link[j] = p;return 1;}}}return 0;}int main(){int h,t,w,i,j,k,xx,yy,cnt,sum;scanf(“%d”,&t);while(t–){memset(mp,false,sizeof(mp));tp = 0;scanf(“%d %d”,&h,&w);for(i = 1; i <= h; ++i){scanf(“%s”,Map[i]+1);}n = h*w;dir[0] = -w;dir[1] = -1;dir[2] = w;dir[3] = 1;sum = n;for(i = 1; i <= h; ++i){for(j = 1; j <= w; ++j,++tp){if(Map[i][j] == ‘o’){sum–;continue;}for(k = 0; k < 4; ++k){xx = i + dirx[k];yy = j + diry[k];if(tp + dir[k] >= 0 && tp + dir[k] < n){if(Map[xx][yy] == ‘*’)mp[tp][tp+dir[k]] = true;}}}}memset(link,-1,sizeof(link));cnt = 0;for(i = 0; i < n; ++i){memset(vis,0,sizeof(vis));if(can(i)) cnt++;}printf(“%d\n”,sum-cnt+cnt/2);}return 0;}
，发光并非太阳的专利，我也可以发光 。
