2020-09-26最小费用最大流问题
http://icpc.upc.edu.cn/problem.php?cid=2587&pid=6
题目描述¶
Bonnie and Clyde have noticed that parallel processing improves throughput so, instead of robbing one bank together, they’ve decided to rob two different banks simultaneously (each robbing one).
They both succeeded and now they need to run to their get-away 1934 Ford Model (730 Deluxe Sedan). There are complications, of course, or the movie won’t be exciting!
The city is in the shape of a matrix with cells. Bonnie and Clyde are in two different cells, and the get-away car is in a different cell as well. Bonnie and Clyde can move in four directions: north, south, east, and west (the border cells of course have fewer move options since they cannot move across the outer walls of the city). Some cells are also blocked, i.e., neither one can move into it.
To put more adventure in the movie, it is also the case that once Bonnie or Clyde moves into a cell, then neither one can move into that cell anymore, i.e., a cell is used at most once. Bonnie and Clyde cannot move into each other’s starting position either.
Given the city map (in the form of a matrix), the location for Bonnie, Clyde, and car, you are to compute the minimum total number of moves needed for both Bonnie and Clyde to get to the car, i.e., the total number of moves made by Bonnie plus the total number of moves made by Clyde.
输入¶
The first input line contains two integers, r and c (2 ≤ r, c ≤ 30), providing the number of rows and columns for the matrix. Each of the next r lines contains c characters, starting in column 1; this is the input matrix. There will be exactly one “B” (Bonnie’s starting location), one “C” (Clyde’s starting location), and one “F” (where the get-away Ford car is) in the input maze. The remaining cells will be “.” (empty cell – one can move into) or “x” (blocked – one cannot move into).
输出¶
Print the minimum total number of moves needed for both Bonnie and Clyde to get to the car. If they cannot get to the car, print -1. Note that when one reaches the car, he/she stops moving.
样例输入¶
样例输出¶
提示¶
Bonnie can reach the car with 4 moves and Clyde can reach the car with 5 moves, for a total of 9 moves.
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
struct node
{
int next;
int flow;
int dis;
int to;
};
int head[100500]= {0};
node edge[100500]= {0};
int dis[100500]= {0};
int pre[100500]= {0};
int vis[100500]= {0};
int last[100500]= {0};
int flow[100500]={0};
char g[1000][1000]= {0};
int n,m,s,t,cnt=-1,maxflow=0,mincost=0;
int num(int i,int j)
{
return i*m+j;
}
int add(int from,int to,int flow,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].flow=flow;
edge[cnt].dis=dis;
head[from]=cnt;
}
queue<int>w;
bool spfa(int start,int end1)
{
w.push(start);
memset(dis,0x3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(flow,0x3f3f3f,sizeof(flow));
pre[end1]=-1;
vis[start]=1;
dis[start]=0;
while(!w.empty())
{
int now=w.front();
w.pop();
vis[now]=0;
for(int i=head[now]; i!=-1; i=edge[i].next)
{
//cout<<i<<endl;
if(edge[i].flow>0&&dis[edge[i].to]>dis[now]+edge[i].dis)
{
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);
if(!vis[edge[i].to])
{
vis[edge[i].to]=1;
w.push(edge[i].to);
}
}
}
}
return pre[end1]!=-1;
}
int MCMF()
{
while(spfa(s,t))
{
maxflow+=flow[t];
mincost+=dis[t]*flow[t];
int now=t;
while(now!=s)
{
edge[last[now]].flow-=flow[t];
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
s=n*m+200,t=n*m+100;
for(int i=1; i<=n; i++)
{
scanf("%s",g[i]+1);
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(g[i][j]=='x')
continue;
if(j>1&&g[i][j-1]!='x')
{
add(num(i,j),num(i,j-1),1,1);
add(num(i,j-1),num(i,j),0,-1);
}
if(i>1&&g[i-1][j]!='x')
{
add(num(i,j),num(i-1,j),1,1);
add(num(i-1,j),num(i,j),0,-1);
}
if(j<m&&g[i][j+1]!='x')
{
add(num(i,j),num(i,j+1),1,1);
add(num(i,j+1),num(i,j),0,-1);
}
if(i<n&&g[i+1][j]!='x')
{
add(num(i,j),num(i+1,j),1,1);
add(num(i+1,j),num(i,j),0,-1);
}
if(g[i][j]=='F')
{
add(s,num(i,j),2,0);
add(num(i,j),s,0,0);
}
if(g[i][j]=='C'||g[i][j]=='B')
{
add(num(i,j),t,1,0);
add(t,num(i,j),0,0);
}
}
}
MCMF();
// cout<<maxflow<<" "<<mincost<<endl;
if(maxflow!=2)
printf("-1\n");
else
printf("%d\n",mincost);
}