poj 3020 Antenna Placement //二分图匹配，匈牙利算法 （模板）
题意：给一个地图，其中相邻（上下左右）两个'*'可以匹配，求最多可以匹配几个。
匈牙利算法，复杂度O（n*m）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<climits> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e4+1; char mp[100][100]; int go[4][2]={0,1,1,0,-1,0,0,-1}; int used[MX],match[MX],n,m,cnt; vector<int>g[MX]; int toint(int x,int y){ return x*m+y; } /*void topoint(int &x,int &y,int p){ x=p/n,y=p-p/n*n; }*/ bool HA(int v){ //dfs找增广路 used[v]=1; for(int i=0;i<g[v].size();i++){ int u=g[v][i],w=match[u]; if(w<0||!used[w]&&HA(w)){ match[u]=v; match[v]=u; return 1; } } return 0; } int bipartite_matching(){ //记得加入双向边 int res=0; memset(match,-1,sizeof(match)); for(int v=0;v<n*m;v++){ //直接按照时间点往后面找 if(match[v]<0){ memset(used,0,sizeof(used)); if(HA(v)) res++; } } return res; } void init(){ for(int i=0;i<=n*m;i++)g[i].clear(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(mp[i][j]=='*'){ cnt++; for(int k=0;k<4;k++){ int th=i+go[k][0],tl=j+go[k][1]; if(th<0||tl<0||th>=n||tl>=m)continue; if(mp[th][tl]=='o')continue; int st=toint(i,j),ed=toint(th,tl); g[st].push_back(ed); } } } } } int main(){ int T;scanf("%d",&T);while(T--){ scanf("%d%d",&n,&m);cnt=0; for(int i=0;i<n;i++)cin>>mp[i]; init(); int pairred=bipartite_matching(); printf("%d\n",cnt-pairred); } return 0; }
