自动搬运

查看原文

来自洛谷，原作者为

	Rhodoks 一旦尝试过飞行的滋味，便会永远仰望天空。因为你曾去过那里，并且渴望回到那里。

搬运于2025-08-24 21:23:04，当前版本为作者最后更新于2018-12-10 19:38:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

  来一篇带注释的题解（手动滑稽）。

  称每一段朝上的墙为横墙，每一段朝左的墙为竖墙。那么每一个侍卫都对应唯一一段横墙和竖墙，而两个侍卫不互相攻击的条件就是这两段墙所对的空地上没有其他侍卫。将每一格空地对应的横墙和竖墙连一条边，问题就转化成了二分图最大匹配问题。

  图中诸如“横/竖 xy”代表位于空格（x，y）下/右方的横/竖墙。

  建立网络流模型求解二分图最大匹配，超源连所有横墙，横墙通过空格连对应竖墙，竖墙连超汇，权值均为1。

  放张图瞧瞧（图中“点xy“类型的节点在建图中是没有的，这里只是方便理解加上来）。

  顺便说一句，https://csacademy.com/app/graph_editor/ 这玩意画图真好用。

  建图时，对于二维平面内的墙，我们可以把坐标映射到一维上，由于N,M<=200，所以我们令z=(x-1)*200+y，横墙（x,y）对应结点为p，竖墙（x,y）对应结点为p+40000，令超级源点为0，超级汇点为80001，跑最大流即可。

  上代码咯，有注释的代码。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream> 
#include <queue>
#define MAXM 100100
#define MAXN 202
#define MAXN2 202*202
using namespace std;

const int INF=2147483647;

int wall[MAXN][MAXN][2]; //记录空格对应的横墙和竖墙 
int castle[MAXN][MAXN]; //城堡地形图 
int n,m,s,t; //n：x方向长度  m：y方向长度 这里注意，和题目给的是反过来的  s和t为超源超汇 
int maxflow=0;
int idbegin;  //从这个编号开始的边全部是连接竖墙和横墙的边 

struct EDGE
{
	int from,to,weight,next;
}edge[MAXM<<1]; //链式前向星存图 

int head[MAXN2<<1];
int deep[MAXN2<<1];
int cnt=0;

inline void add(int x,int y,int w)
{
	edge[cnt].from=x;
	edge[cnt].to=y;
	edge[cnt].weight=w;
	edge[cnt].next=head[x];
	head[x]=cnt++;
}

inline int convert(int x,int y)  //把二维的坐标映射到一维 
{
	return (x-1)*200+y;
}

void input()
{
	for (int i=0;i<=MAXN2<<1;i++)
		head[i]=-1;
	s=0;
	t=80001;
	cin>>n>>m;
	
	
	for (int i=0;i<=n+1;i++)
	{
		castle[i][0]=2; 
		castle[i][m+1]=2; 
	}
	for (int i=1;i<=m+1;i++)
	{
		castle[0][i]=2; 
		castle[n+1][i]=2; 
	} //这里把城堡用墙先围上一圈 
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d",&castle[i][j]); //读入 

	int poswall;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (castle[i][j]!=2)
			{
				poswall=convert(i,j);
				if (castle[i+1][j]==2) //如果（i,j)下方有堵墙 
				{
					add(s,poswall,1);
					add(poswall,s,0); //从超源往这堵墙连边 
					for (int k=i;castle[k][j]!=2;k--) //往上走，记录在wall数组里 
						wall[k][j][0]=poswall;
				}
				if (castle[i][j+1]==2) //如果（i,j)右方有堵墙
				{
					add(poswall+40000,t,1); //竖墙是要加上40000的 
					add(t,poswall+40000,0);
					int poswall=convert(i,j);
					for (int k=j;castle[i][k]!=2;k--)
						wall[i][k][1]=poswall;
				}
			}
	idbegin=cnt; //记录此时的cnt，最终寻找有流边的时候从这里开始找就行了 
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (castle[i][j]==0) //如果遇到空地，从对应横墙往对应竖墙连边 
			{
				add(wall[i][j][0],wall[i][j][1]+40000,1);
				add(wall[i][j][1]+40000,wall[i][j][0],0);
			}
}

bool bfs() //dinic算法的bfs部分，求出每个点的deep ，如果到不达汇点说明已经满流 
{
	int cur;
	queue <int> q;
	for (int i=0;i<=80001;i++)
		deep[i]=-1;
	deep[s]=0;
	q.push(s);
	while (!q.empty())
	{
		cur=q.front();
		q.pop();
		for (int i=head[cur];~i;i=edge[i].next)
			if (!~deep[edge[i].to] && edge[i].weight)
			{
				deep[edge[i].to]=deep[cur]+1;
				q.push(edge[i].to);
			}
	}
	if (~deep[t])
		return true;
	else
		return false;
}

int dfs(int cur,int limit) //dinic的dfs部分，寻找可行流
{
	if (!limit || cur==t)
		return limit;
		
	int flow=0;
	int f;
	
	for (int i=head[cur];~i;i=edge[i].next)
	{
		if (deep[edge[i].to]==deep[cur]+1 && (f=dfs(edge[i].to,min(limit,edge[i].weight))))
		{
			flow+=f;
			limit-=f;
			edge[i].weight-=f;
			edge[i^1].weight+=f;
			if (!limit) break;
		}
	}
	if (!flow) deep[cur]=-1;
	return flow;
}

int dinic() //能看到这题应该dinic已经掌握了，不再赘述，如不然请先A了模板题 
{
	while (bfs())
		maxflow+=dfs(s,INF);
	return maxflow;
}

int main()
{
	input();
	dinic();
	cout<<maxflow<<endl;
	for (int i=idbegin;i<cnt;i+=2) //扫描所有正向边 
		if (edge[i].weight==0) //如果有流通过，输出对应竖墙的x坐标和横墙的y坐标 
			cout<<(edge[i].to-40000-1)/200+1<<' '<<(edge[i].from-1)%200+1<<endl; //反过来映射的时候要小心 
	return 0;
}