自动搬运

查看原文

来自洛谷，原作者为

	Akoasm_X AFO|如果我失去了我，那还剩下什么

搬运于2025-08-24 21:48:04，当前版本为作者最后更新于2021-03-28 19:55:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

网络流24题的题解我之前也有写过一些，里面也有网络流知识的教学，讲得好不好看看也无妨 传送门

12ms，发现跑得蛮快的，分享一下做法(2021.3.28)

首先这题要用到网络流就不用我多说了，题目限制了两个量：车的数量 和 最大的总价值。

1. 我们把车的数量当作流量，最大总价值当作花费，就变成了最大费用最大流，接着我们在加边时把花费取负，加进去跑最小费用最大流，此时的最小费用再取负就是最大花费。当然，最大花费是多少并不重要

2. 对于岩石标本来讲，点权为1的价值，但只能拿一次，于是我把点拆开计算，从入点向出点连边，容量为 1 ，花费为 -1。对于没有障碍的点，也从入点向出点连边，容量无穷大，但因为没有标本可以采集所以花费为0

3. 探测车行走的话，就是从左侧/上侧的出点向右侧/下侧的入点连边，这个边对车没有限制，所以容量无穷大，花费为0

4. 从虚拟源点向（ 1，1 ）的入点连边，容量为 探测车 的数量，再从（ m , n ）的出点向虚拟汇点连边，容量也是 探测车 的数量，花费都是0

5. 然后愉快地跑完MCMF后，发现并不要求输出花费而是输出路径，行吧，下一题

6. 在计算过程中会修改边的容量，修改过就表示我们走过去了，所以我就把边枚举了出来，建了个新图，跑了一遍dfs

7. 但是也不用枚举所有边，指枚举点和点之间的连边就可以了，枚举出点，找出入点，由于这些边一开始容量都是 inf ,后来修改过程中 inf - va（现在的容量）就代表这条路径所经过的探测车有几个，那就在新图上连边，边权是 inf - va

8. 之后就跑一边dfs就可以了,如果还是不清楚可以看代码注释

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10021;
const int maxm = 10021;
const int inf = 2147483647;
int n,m,cnt,str,end,tot = -1,maxcost,p;
int head[maxn],pre[maxn],last[maxn],flow[maxn],d[maxn],pos[50][50];
bool vis[maxn],v[maxn];
struct node
{
	int net,va,cost,to;
}data[maxm<<3];

int read() 
{
	int res=0;
	char c=getchar();
	while (c<'0'||c>'9')
		c=getchar();
	while (c>='0'&&c<='9')
	{
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}

void add(int a,int b,int va,int cost)
{
	data[++tot].cost = cost;
	data[tot].net = head[a];
	data[tot].to = b;
	data[tot].va = va;
	head[a] = tot;
	data[++tot].cost = -cost;
	data[tot].net = head[b];
	data[tot].to = a;
	data[tot].va = 0;
	head[b] = tot;
}

bool SPFA()
{
	memset(d,0x3f,sizeof(d));
	memset(flow,0x3f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(str);
	vis[str] = 1;
	d[str] = 0;
	pre[end] = -1;
	while(!q.empty())
	{
		int from = q.front();q.pop();
		vis[from] = 0;
		for(int i=head[from];i!=-1;i=data[i].net)
		{
			int to = data[i].to ;
			int va = data[i].va ;
			int cost = data[i].cost ;
			if(va&&d[to]>d[from]+cost)
			{
				d[to] = d[from]+cost;
				pre[to] = from; 
				last[to] = i;
				flow[to] = min(flow[from],va); 
				if(!vis[to])
				{
					vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	return pre[end] != -1;
}

void MCMF()
{
	while(SPFA())
	{
		int now = end;
		maxcost += flow[end]*d[end];
		while(now!=str)
		{
			data[last[now]].va -= flow[end];
			data[last[now]^1].va += flow[end];
			now = pre[now];
		}
	}
}

void print(int id,int x)
{
	int temp = x - 2 * n * m;//真实的坐标点
	for(int i=head[x];i!=-1;i=data[i].net)
	{
		int to = data[i].to ;
		int va = data[i].va ;
		if(!va)	continue;//表示这条边已经不能有车通过了 
		int tt = to - 2 * n * m;
		if(temp+1==tt)	printf("%d 1\n",id);//向右 
		else			printf("%d 0\n",id);//向下 
		data[i].va--;
		print(id,to);
		break;
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	cnt = read();m = read();n = read();
	str = 3 * n * m + 1;end = 3 * n * m + 2;
	//区间[1,n*m]内是入点，(n*m,2*n*m]是出点，(2*n*m,3*n*m]是新图上的点 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			pos[i][j] = ++p;//先给每个点一个编号 
	add(str,1,cnt,0);
	add(2*n*m,end,cnt,0);//对应分析4 
	for(int i=1;i<=n;i++)//对应分析2 
	{
		for(int j=1;j<=m;j++)
		{
			int x = read();
			if(x==2)	add(pos[i][j],pos[i][j]+n*m,1,-1);
			if(x!=1)	add(pos[i][j],pos[i][j]+n*m,inf,0);
			else	v[pos[i][j]] = 1;//标记一下不能走的边 
		}
	}
	for(int i=1;i<=n;i++)//对应分析3 
		for(int j=2;j<=m;j++)
			add(pos[i][j-1]+n*m,pos[i][j],inf,0);
	for(int i=2;i<=n;i++)
		for(int j=1;j<=m;j++)
			add(pos[i-1][j]+n*m,pos[i][j],inf,0);
	MCMF();//愉快地跑一边MCMF，其中过程很常规 
	for(int x=1+n*m;x<2*n*m;x++)
	{//枚举出点 
		if(v[x-n*m])	continue;//跳过障碍 
		for(int i=head[x];i!=-1;i=data[i].net)
		{
			int va = data[i].va ;
			int to = data[i].to ;
			if(to+n*m==x)	continue;//去掉连向自身的入点 
			if(va==inf)	continue;//去掉不会有车经过的边 
			if(to!=end)
				add(x+m*n,to+2*n*m,inf-va,0);
		}
	}
	for(int i=1;i<=cnt;i++)//dfs求解即可 
		print(i,1+2*n*m);
	return 0;
}

有何不当之处还请大佬指出，不妨留个赞，感谢支持！