Cost flow

General idea of the topic

Here is a map of $P \times Q $. There are three kinds of terrain on it:

• $mp[i][j]=0 $, indicating that the $I $row and $j $column of the map are flat terrain, which can be passed at will.

• $mp[i][j]=1 $, indicating that the $I $row and $j $column of the map are obstacle terrain and cannot be passed.

• $mp[i][j]=2 $, indicating that the $I $row and $j $column of the map are rock samples, which can be passed at will, but only one pass can be recorded, indicating collection.

Now, there are $n $exploration vehicles. They can only go east or south. You need to get as many rock samples as possible while ensuring that they can reach the destination (Note: if the exploration vehicle does not reach the destination, the rock samples collected by it will be discarded)

Topic analysis

Obviously, this problem can be solved with the maximum cost and maximum flow.

Consider how to create a drawing:

• For each $2 $node, it can only be collected once. We naturally thought of splitting points to solve it. Break $i node into $i node_ 1 $and $i_2 $, the operation of collecting rock samples once is actually in $i_1 $and $i_ There is even a side with a traffic of $1 and a cost of $1 between $2. However, after being collected, the $2 $node can be processed countless times. The corresponding edge construction is to build another edge with positive infinite traffic and $0 $cost.

• For every $1 $node, it is obvious that no point will connect edges to it, and he will not connect edges to any point.

• For each node with a value of $0 $, in fact, in theory, we should not need to dismantle the point, because the point weight of each node is positive infinity except $1 $. It is not necessary to convert the point weight into edge weight to limit the flow, but for convenience, we still divide it into two points, and connect them with an edge with a value of positive infinity and a cost of $0 $.

For details, please refer to the following drawing code:

//Mapping (summary points: 2*p*q, source point: 0, sink point: 2*p*q+1)
//Take all points apart
//Connection between disassembly points: 0 - > 0, flow INF, cost 0,1 - > 1, flow 1, cost 1 
for(register int i=1;i<=p;i++){
	for(register int j=1;j<=q;j++){
		if(mp[i][j]==1) continue; //No point is connected with the obstacle
		int u=Get_id(i,j),v; //u represents the current node number and v represents the target node number 
		//Set the disassembly point of node i as I ' 
		//Outward edge: u '- > V
		for(register int k=0;k<=1;k++){
			int nx=i+dx[k],ny=j+dy[k];
			if(nx>p||ny>q) continue; //Not beyond the boundary
			if(mp[nx][ny]==1) continue; //obstacle 
			v=Get_id(nx,ny);
			Add(u+p*q,v,INF,0),Add(v,u+p*q,0,0);
		}
		//Connect yourself: U - > u ' 
		//For rock specimens, two sets of edges are established. The first set of current limiting 1 that contributes to the answer indicates that it can only be collected once
		//The second group shows that rock specimens can arrive at any time like ordinary ground 
		if(mp[i][j]==2) Add(u,u+p*q,1,1),Add(u+p*q,u,0,-1); //The current node is rock specimen 
			//Any point outside the obstacle can be reached at will 
		Add(u,u+p*q,INF,0),Add(u+p*q,u,0,0);
	}
}

How to print paths

For the path, we only need to run $DFS $from $(1,1) $on the residual graph, find the edges flowing through and print them

Reference codes are as follows:

inline void DFS(int x,int y,int u,int k)
{
	int kx,ky,mov;
	for(register int i=first[u];i!=-1;i=nex[i]){
		int to=v[i];
		if(to==s||to==t||to==u-p*q||!w[i^1]) continue;
		w[i^1]--; //The number of passes --, known as 0, indicates that all the detection vehicles passing on the side have been considered
		if(to>p*q) { DFS(x,y,to,k); return; } //If i 'is reached, it is the dismantling point connecting other points 
		if(to==Get_id(x,y)+1) kx=x,ky=y+1,mov=1; //Determine which point to go 
		else kx=x+1,ky=y,mov=0;
		printf("%d %d\n",k,mov);
		DFS(kx,ky,to+p*q,k); //recursion 
		return;
	}
}

be careful

The input order of $p$and $q$in this question, the column to be input first, and then the row to be input, I found it after adjusting it for a year. I was really impressed.

CODE

#include <bits/stdc++.h>
using namespace std;
const int N=1e2,INF=0x3f3f3f3f;
const int dx[2]={0,1},dy[2]={1,0};
int n,p,q;
int s,t,ans,maxf;
int mp[N][N];
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int tot=-1,v[N*N*N],w[N*N*N],pay[N*N*N],nex[N*N*N],first[2*N*N];
inline void Add(int x,int y,int z,int c)
{
	nex[++tot]=first[x];
	first[x]=tot;
	v[tot]=y,w[tot]=z,pay[tot]=c;
}
inline int Get_id(int x,int y) { return (x-1)*q+y; }
bool vis[2*N*N];
//Min[i] represents the one with the smallest side flow passing through the arrival point I 
int dis[2*N*N],pre[2*N*N],Min[2*N*N];
inline bool SPFA()
{
	for(register int i=s;i<=t;i++) vis[i]=false;
	for(register int i=s;i<=t;i++) dis[i]=-INF;
	queue<int> q; q.push(s);
	vis[s]=true,dis[s]=0,Min[s]=INF;
	while(!q.empty()){
		int now=q.front(); q.pop();
		vis[now]=false;
		for(register int i=first[now];i!=-1;i=nex[i]){
			int to=v[i];
			if(!w[i]) continue; //No flow 
			if(dis[to]<dis[now]+pay[i]){ //Longest path update 
				dis[to]=dis[now]+pay[i];
				Min[to]=min(Min[now],w[i]);
				pre[to]=i;
				if(!vis[to]) q.push(to),vis[to]=true;
			}
		}
	}
	return dis[t]!=-INF;
}
inline void EK()
{
	while(SPFA()){
		maxf+=Min[t];
		int temp=t,i;
		while(temp!=s){
			i=pre[temp];
			w[i]-=Min[t]; 
			w[i^1]+=Min[t];
			temp=v[i^1];
		}
	}
}
inline void DFS(int x,int y,int u,int k)
{
	int kx,ky,mov;
	for(register int i=first[u];i!=-1;i=nex[i]){
		int to=v[i];
		if(to==s||to==t||to==u-p*q||!w[i^1]) continue;
		w[i^1]--;
		if(to>p*q) { DFS(x,y,to,k); return; } //If i 'is reached, it is the dismantling point connecting other points 
		if(to==Get_id(x,y)+1) kx=x,ky=y+1,mov=1; //Determine which point to go 
		else kx=x+1,ky=y,mov=0;
		printf("%d %d\n",k,mov);
		DFS(kx,ky,to+p*q,k); //recursion 
		return;
	}
}
int main()
{
	memset(first,-1,sizeof(first));
	n=read(),q=read(),p=read();
	for(register int i=1;i<=p;i++)
		for(register int j=1;j<=q;j++)  mp[i][j]=read();
	s=0,t=2*p*q+1;
	//Mapping (summary points: 2*p*q, source point: 0, sink point: 2*p*q+1)
	//Take all points apart
	//Connection between disassembly points: 0 - > 0, flow INF, cost 0,1 - > 1, flow 1, cost 1 
	for(register int i=1;i<=p;i++){
		for(register int j=1;j<=q;j++){
			if(mp[i][j]==1) continue; //No point is connected with the obstacle
			int u=Get_id(i,j),v; //u represents the current node number and v represents the target node number 
			//Set the disassembly point of node i as I ' 
			//Outward edge: u '- > V
			for(register int k=0;k<=1;k++){
				int nx=i+dx[k],ny=j+dy[k];
				if(nx>p||ny>q) continue; //Not beyond the boundary
				if(mp[nx][ny]==1) continue; //obstacle 
				v=Get_id(nx,ny);
				Add(u+p*q,v,INF,0),Add(v,u+p*q,0,0);
			}
			//Connect yourself: U - > u ' 
			//For rock specimens, two sets of edges are established. The first set of current limiting 1 that contributes to the answer indicates that it can only be collected once
			//The second group shows that rock specimens can arrive at any time like ordinary ground 
			if(mp[i][j]==2) Add(u,u+p*q,1,1),Add(u+p*q,u,0,-1); //The current node is rock specimen 
			//Any point outside the obstacle can be reached at will 
			Add(u,u+p*q,INF,0),Add(u+p*q,u,0,0);
		}
	}
	if(mp[1][1]!=1) Add(s,1,n,0),Add(1,s,0,0);
	if(mp[p][q]!=1) Add(Get_id(p,q)+p*q,t,n,0),Add(t,Get_id(p,q)+p*q,0,0);
	EK();
	for(register int i=1;i<=maxf;i++) DFS(1,1,1,i);
	return 0;
}