标签：二分 ma ABC274G int 303 vis 木板

date: 2022-10-23
alias: P6062

template

[[Hungarian Algorithm]]

每个点可能在两个方向上的木板上，

所以可以转化为二分图，一块尽可能大的木板看作一个点，两个方向上的木板是天然的两个集合
点转化为两块木板间的边，现在就能转化为一个二分图了

要放最少的木板，同时要使所有边至少有一端被覆盖

这就是二分图的最小点覆盖问题

于是跑一遍匈牙利算法就行

#include<bits/stdc++.h>
using namespace std;
const int N=90004;
int n,m,cnt1,cnt2,ans,vis[N],ma[N],co[303][303];
vector<int>g[N];
char o[303][303];
int dfs(int u){
	for(auto v:g[u])if(!vis[v])if(vis[v]=1,!ma[v]||dfs(ma[v]))return ma[v]=u,1;return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf(" %c",&o[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(o[i][j]=='.')cnt1+=o[i][j-1]!='.',co[i][j]=cnt1;
	for(int j=1;j<=m;j++)for(int i=1;i<=n;i++)if(o[i][j]=='.')cnt2+=o[i-1][j]!='.',g[co[i][j]].push_back(cnt2);
	for(int i=1;i<=cnt1;i++){
		for(int j=1;j<=cnt2;j++)vis[j]=0;
		ans+=dfs(i);
	}
	printf("%d",ans);
}

一开始是打成邻接矩阵的，能过P6062

然后AT上得写成邻接表，不然空间会爆，这也是为什么我赛时没贺下来

标签：二分,ma,ABC274G,int,303,vis,木板
From： https://www.cnblogs.com/-WD-/p/16973108.html