part1 费用流建图
比较显然,把车的数量当成流量,把捡到的石头数量当成费用。然后跑最大费用最大流。
因为费用是针对点而不是边,所以要拆点,每个点分为入点和出点。
- 对于向下走,向右走建边:从起点的出点向终点的入点连边,容量为 \(inf\),费用为 \(0\)。
- 对于每一个格子,如果当前格子是石头,那么我们想要的效果是,可以经过无数次,但是只有第一次能得到费用,所以我们把经过这个点的情况分为两种:第一次和第二次及之后。所以从入点到出点建两条边,一条边容量为 \(1\),费用为 \(1\),一条边容量为 \(inf\),费用为 \(0\)。
- 对于每一个格子,如果当前点是障碍,不连接入点和出点,以达到不能经过的效果。
- 对于每一个格子,如果当前格子是空格,从入点到出点建一条容量为 \(inf\),费用为 \(0\)。表示可以无数次经过,但是没有费用。
part2 找方案
网络流找方案的做法是什么?在残留网络上,如果一条正向边对应的反向边的容量大于 \(0\),那么流经这条边的流量就为其反向边的容量。
费用流也是一样的。
所以我们找到那些有流量的边,这些边就是机器人经过的边,建一个新图,在图上跑 DFS 即可。
part3 一些细节
注意到题目中的要求是 “使到达传送器的探测车的数量最多,而且探测车采集到的岩石标本的数量最多”。
在费用流中,如果没有负权边,那么一定是流量越大,最大费用越大。相应的,在本题中,探测车的数量越多,采到的岩石标本一定单调不减,所以直接跑最大费用流是没有问题的。
注意原题中格子的标号方式与普遍的标号方式不同。
Code
// 2024.2.1 20.02
// 20:35 first test
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MAXM=1e5+5;
struct E{int nxt,to,cap,w;}e[MAXM];
int head[MAXN];
int cnt=1;
void add(int u,int v,int cap,int w){
e[++cnt]={head[u],v,cap,w};head[u]=cnt;
e[++cnt]={head[v],u,0,-w};head[v]=cnt;
}
int dis[MAXN],flow[MAXN];
bool in[MAXN];
int las[MAXN];
const int INF=0x3f3f3f3f;
int n,S,T;
bool spfa(){
queue<int> q;
for(int i=1;i<=n;i++) dis[i]=-INF,flow[i]=0;
flow[S]=INF,dis[S]=0;
q.push(S),in[S]=1;
while(!q.empty()){
int u=q.front();q.pop();in[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w&&e[i].cap){
dis[v]=dis[u]+e[i].w;
flow[v]=min(flow[u],e[i].cap);
las[v]=i;
if(!in[v]) q.push(v),in[v]=1;
}
}
}
return dis[T]>-INF;
}
void EK(int &ans,int &cost){
ans=cost=0;
while(spfa()){
int dlt=flow[T];
ans+=dlt,cost+=dis[T]*dlt;
int u=T;
while(u!=S){
int i=las[u];
e[i].cap-=dlt,e[i^1].cap+=dlt;
u=e[i^1].to;
}
}
}
int N,M,K;
int id(int x,int y,int z){return (x-1)*M+y+z*N*M;}
int dir[4][2]={{0,1},{1,0}};
int mp[55][55];
#define pii pair<int,int>
#define fi first
#define se second
vector<pii> G[MAXN];
int Print;
void dfs(int u){
int y=(u%M==0?M:u%M);
for(pii &t:G[u]){
int v=t.fi;
if(!t.se) continue;
int ty=(v%M==0?M:v%M);
if(y==ty) printf("%d 0\n",Print);
else printf("%d 1\n",Print);
dfs(v);
t.se--;
break;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
scanf("%d%d%d",&K,&M,&N);
n=N*M*2+2;S=n-1,T=n;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
int v;scanf("%d",&v);
if(v==1) continue;
mp[i][j]=v;
add(id(i,j,0),id(i,j,1),INF,0);
if(v==2) add(id(i,j,0),id(i,j,1),1,1);
for(int k=0;k<=1;k++){
int di=i+dir[k][0],dj=j+dir[k][1];
if(di<1||dj<1||di>N||dj>M) continue;
add(id(i,j,1),id(di,dj,0),INF,0);
}
}
}
add(S,id(1,1,0),K,0);
add(id(N,M,1),T,K,0);
int ans,cost;
EK(ans,cost);
for(int i=2;i<=cnt;i+=2){
int u=e[i^1].to,v=e[i].to;
if(v>=1&&v<=N*M&&u>=N*M+1&&u<=N*M*2){//从出点到入点的边
if(e[i^1].cap) G[u-M*N].push_back({v,e[i^1].cap});
}
}
for(Print=1;Print<=ans;Print++){
dfs(1);
}
return 0;
}
标签:费用,P3356,int,题解,cnt,cost,MAXN,dlt,火星
From: https://www.cnblogs.com/bwartist/p/18002150