# 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.

## 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];
{
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));
for(register int i=1;i<=p;i++)
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);
}
//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
//Any point outside the obstacle can be reached at will
}
}
EK();
for(register int i=1;i<=maxf;i++) DFS(1,1,1,i);
return 0;
}


Tags: network-flows

Posted by TheLoveableMonty on Mon, 18 Apr 2022 07:02:08 +0930