题意:给出一些城市的坐标,每个信号基站可以覆盖两个相邻的点,问最少要建多少个基站。
思路:我们要尽可能多的建立能覆盖两个城市的基站(二分匹配最大匹配),剩下的城市每个城市建立一个基站。先求出最大匹 配数k。n-k*2+k=n-k;
#include<stdio.h> #include<string.h> const int N=500; int head[N],num,match[N],link[N],map[50][50]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; struct edge { int st,ed,next; }e[N*N]; void addedge(int x,int y) { e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++; } int find(int u) { int v,i; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].ed; if(link[v]==1)continue; link[v]=1; if(match[v]==-1||find(match[v])==1) { match[v]=u; return 1; } } return 0; } int main() { int i,n,k,j,m,t,sum,p,x,y; char str[50][20]; scanf("%d",&t); while(t--) { num=0;k=1; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(i=0;i<n;i++) { scanf("%s",str[i]); for(j=0;j<m;j++) if(str[i][j]=='*') map[i][j]=k++; } for(i=0;i<n;i++) for(j=0;j<m;j++) if(str[i][j]=='*') for(p=0;p<4;p++) { x=i+dir[p][0]; y=j+dir[p][1]; if(x>=0&&x<n&&y>=0&&y<m&&str[x][y]=='*') addedge(map[i][j],map[x][y]); } memset(match,-1,sizeof(match)); sum=0;k--; for(i=1;i<=k;i++) { memset(link,0,sizeof(link)); sum+=find(i); } printf("%d\n",k-(sum/2)); } return 0; }