[LibreOJ Round #11]Misaka Network 与测试

Misaka Network 与测试

题解

其实是很简单的一道二分图匹配，是谁拿着网络流在哪里瞎想

应该很容易发现，对于任何为$2$的妹妹，拿出来单独作矩阵都一定是最优的。因为如果有任何一种选择方法包含了这个妹妹，都不会超过将其拿出来的贡献。
同理，对于任何一对相邻的$1,3$，都应该将其连在一起，所以我们只用去考虑如何将$1$与$3$相连。
于是就很自然的想到了二分图匹配，将$1$与$3$划作图的两侧，在相邻的$1$与$3$间连边，然后跑匈牙利，看能够匹配出多少对$1$和$3$，在加上$2$的个数即可。

时间复杂度$O\left(n^2{m}^2\right)$看起来跑不过，但其实是绰绰有余的。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 100005
#define reg register
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL inf=0x7f7f7f7f7f7f;
template<typename _T>
inline void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while('0'>s||'9'<s){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
int n,m,head[MAXN],tot,cnt1,cnt3,maze[MAXN],ans,id[MAXN],p[MAXN];
bool vis[MAXN];int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
struct edge{int to,nxt;}e[MAXN<<2];
inline void addEdge(const int u,const int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
inline bool match(const int x){
	vis[x]=1;
	for(reg int i=head[x];i;i=e[i].nxt)
		if(p[e[i].to]==-1||(!vis[p[e[i].to]]&&match(p[e[i].to])))
			return (p[e[i].to]=x,1);
	return 0;
}
inline void sakura(){
	for(reg int i=1;i<=cnt1;++i)p[i]=-1;
	for(reg int i=1;i<=cnt3;++i){
		for(reg int j=1;j<=cnt3;++j)vis[j]=0;
		if(match(i))++ans;
	}
}
inline int Id(const int x,const int y){return (x-1)*m+y;}
signed main(){
	read(n);read(m);
	for(reg int i=1;i<=n;++i){
		scanf("\n");
		for(reg int j=1;j<=m;++j){
			char ch;ch=getchar();
			if(ch=='2')++ans;
			if(ch=='1')id[Id(i,j)]=++cnt1,maze[Id(i,j)]=-1;
			if(ch=='3')id[Id(i,j)]=++cnt3,maze[Id(i,j)]=1;
		}
	}
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=m;++j){
			if(maze[Id(i,j)]^1)continue;
			for(reg int k=0;k<4;++k){
				int tx=i+dx[k],ty=j+dy[k];
				if(tx<1||tx>n||ty<1||ty>m)continue;
				if(maze[Id(tx,ty)]==-1)addEdge(id[Id(i,j)],id[Id(tx,ty)]);
			}	
		}
	sakura();printf("%d\n",ans);
	return 0;
}

谢谢！！！