題面

題意

給出一張地圖,上面有一些石塊或障礙,現在有一些運載車從左上角出發,要去右下角,只能向右或向下走,每個石塊只能收集一次,輸出收集到最多石塊的路徑.

做法

多個運載車,不難想到是網絡流,但難點在于每個石塊最多收集一次,而且要收集最多石塊.
可以用費用流來做,每個點拆成兩個入點向出點連一條流量為INF,費用為0的邊,如果該地有石塊,則再連一條流量為1,費用為-1的邊,最后跑費用流,再用dfs輸出路徑即可.

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define N 20010 #define INF 0x3f3f3f3f #define zh(i,j) ((i-1)*n+j) using namespace std;int n,m,k,ans,bb=1,first[N],s,t,last[N],B[N],d[N],mf,mm[40][40]; bool in[N]; struct Bn {int to,next,quan,cst; } bn[1001000]; queue<int>que;inline void add(int u,int v,int w,int z) {bb++;bn[bb].to=v;bn[bb].next=first[u];bn[bb].quan=w;bn[bb].cst=z;first[u]=bb; }inline void ad(int u,int v,int w,int z) { // cout<<u<<" "<<v<<" "<<w<<" "<<z<<endl;add(u,v,w,z);add(v,u,0,-z); }inline bool bfs() {int p,q,mn=INF;for(; !que.empty(); que.pop());memset(d,0x3f,sizeof(d));que.push(s);d[s]=0;for(; !que.empty();){q=que.front();que.pop();in[q]=0;for(p=first[q]; p!=-1; p=bn[p].next){if(d[bn[p].to]>d[q]+bn[p].cst&&bn[p].quan){d[bn[p].to]=d[q]+bn[p].cst;last[bn[p].to]=q;B[bn[p].to]=p;if(!in[bn[p].to]){in[bn[p].to]=1;que.push(bn[p].to);}}}}if(d[t]==INF) return 0;for(p=t; p!=s; p=last[p]){mn=min(mn,bn[B[p]].quan);}ans+=mn*d[t];mf+=mn;for(p=t; p!=s; p=last[p]){bn[B[p]].quan-=mn;bn[B[p]^1].quan+=mn;}return 1; }void df(int now,int u) {if(now==2*m*n) return;int p,q;for(p=first[now];p!=-1;p=bn[p].next){if(bn[p].quan!=INF&&bn[p].quan>100){bn[p].quan++;printf("%d %d\n",u,(now-1)%n<(bn[p].to-1)%n);df(bn[p].to+m*n,u);return;}} }int main() {memset(first,-1,sizeof(first));int i,j,p,q,o,z;cin>>p>>n>>m;ad(s,1,p,0);t=2*m*n;for(i=1;i<=m;i++){for(j=1;j<=n;j++){scanf("%d",&mm[i][j]);ad(zh(i,j),zh(i,j)+m*n,1,-(mm[i][j]==2));ad(zh(i,j),zh(i,j)+m*n,INF,0);}}for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(i<m&&mm[i+1][j]!=1) ad(zh(i,j)+m*n,zh(i+1,j),INF,0);if(j<n&&mm[i][j+1]!=1) ad(zh(i,j)+m*n,zh(i,j+1),INF,0);}}for(; bfs();); // cout<<mf<<" "<<ans; // return 0;for(i=1;i<=p;i++){df(1+m*n,i);} }

總結

以上是生活随笔為你收集整理的洛谷 P3356 火星探险问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。