Antenna Placement POJ - 3020 二分图匹配 匈牙利 拆点建图 最小路径覆盖
题意：图没什么用 给出一个地图 地图上有 点 一次可以覆盖2个连续 的点（ 左右 或者 上下表示连续）问最少几条边可以使得每个点都被覆盖
最小路径覆盖 最小路径覆盖=|G|-最大匹配数 证明：https://blog.csdn.net/qq_34564984/article/details/52778763
证明总的来说就是尽可能多得连边 边越多 可以打包一起处理得点就越多（这里题中打包指连续得两个点只需要一条线段就能覆盖）
拆点思想 ：匈牙利拆了点才好写 不然十分麻烦 简单地说就是点复制一遍 从一边开始匹配
建图：X如果需要覆盖 和它上下左右需要覆盖的点连边 当然这里是和拆完点的另外一个部分的点连边 amp[x][y]两维 分别表示两个集合
答案 最小路径覆盖 = 顶点数 – 最大二分匹配数/2 为什么要除以2呢，因为拆点复制了一遍 需要除回去 比如
1 2 有变 变成
1 和2'
2 和 1'形成了匹配 这样匹配就加倍了 所以除以2就好
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=3000; char mp[maxn][maxn]; int amp[maxn][maxn]; int vis[maxn]; int Hash[maxn][maxn]; int cnt=0; int ans=0; int link[maxn]; int dx[]={ 1,-1,0,0 }; int dy[]={ 0,0,-1,1 }; bool dfs(int x){ for(int i=1;i<=cnt;i++){ if(amp[x][i]&&!vis[i]){ vis[i]=1; if(link[i]==0||dfs(link[i])){ link[i]=x; return 1; } } } return 0; } void solve(){ ans=0; memset(link,0,sizeof(link)); for(int i=1;i<=cnt;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } } int main(){ int t; cin>>t; while(t--){ int n,m; cnt=0; memset(amp,0,sizeof(amp)); cin>>n>>m; for(int i=1;i<=n;i++)scanf("%s",mp[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='*') Hash[i][j]=++cnt; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='*'){ for(int k=0;k<4;k++){ int tx=i+dx[k],ty=j+dy[k]; if(mp[tx][ty]=='*')amp[Hash[i][j]][Hash[tx][ty]]=1; } } } } solve(); cout<<cnt-ans/2<<endl; } return 0; }
查看18道真题和解析
