poj 3020 (二分匹配)
题意：给出一些城市的坐标，每个信号基站可以覆盖两个相邻的点，问最少要建多少个基站。
思路：我们要尽可能多的建立能覆盖两个城市的基站（二分匹配最大匹配），剩下的城市每个城市建立一个基站。先求出最大匹 配数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;}