(http://www.elijahqi.win/2017/12/18/loj6225%E3%80%8C%E7%BD%91%E7%BB%9C%E6%B5%81-24-%E9%A2%98%E3%80%8D%E7%81%AB%E6%98%9F%E6%8E%A2%E9%99%A9%E9%97%AE%E9%A2%98/)
題目描述

火星探險隊的登陸艙將在火星表面著陸，登陸艙內(nèi)有多部障礙物探測車。

登陸艙著陸后，探測車將離開登陸艙向先期到達的傳送器方向移動。

探測車在移動中還必須采集巖石標本。

每一塊巖石標本由最先遇到它的探測車完成采集。

每塊巖石標本只能被采集一次。

巖石標本被采集后，其他探測車可以從原來巖石標本所在處通過。

探測車不能通過有障礙的地面。

本題限定探測車只能從登陸處沿著向南或向東的方向朝傳送器移動，而且多個探測車可以在同一時間占據(jù)同一位置。

如果某個探測車在到達傳送器以前不能繼續(xù)前進，則該車所采集的巖石標本將全部損失。

用一個 P×Q\text{P}\times \text{Q}P×Q 網(wǎng)格表示登陸艙與傳送器之間的位置。登陸艙的位置在 (X1,Y1)(X_1,Y_1)(X?1??,Y?1??) 處，傳送器 的位置在 (XP,YQ)(X_P,Y_Q)(X?P??,Y?Q??) 處。 給定每個位置的狀態(tài)，計算探測車的最優(yōu)移動方案，使到達傳送器的探測車的數(shù)量最多， 而且探測車采集到的巖石標本的數(shù)量最多。

233
輸入格式

文件的第一行為探測車數(shù) car\text{car}car ，第二行為 P\text{P}P 的值，第三行為 Q\text{Q}Q 的值。

接下來的 Q\text{Q}Q 行是表示登陸艙與傳送器之間的位置狀態(tài)的 P×Q\text{P}\times \text{Q}P×Q 網(wǎng)格。

用三個數(shù)字表示火星表面位置的狀態(tài)：0 表示平坦無障礙，1表示障礙，2 表示石塊。
輸出格式

程序運行結(jié)束時，輸出每個探測車向傳送器移動的序列。

每行包含探測車號和一個移動方向，0 表示向南移動，1 表示向東移動。
樣例
樣例輸入

2
10
8
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 1 0 2 0 0 0 0
1 1 0 1 2 0 0 0 0 1
0 1 0 0 2 0 1 1 0 0
0 1 0 1 0 0 1 1 0 0
0 1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

樣例輸出

1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 1
1 1
1 1
1 0
1 0
1 1
1 0
1 0
1 0
2 1
2 1
2 1
2 1
2 0
2 0
2 0
2 0
2 1
2 0
2 0
2 1
2 0
2 1
2 1
2 1

數(shù)據(jù)范圍與提示

1≤P,Q,car≤351\leq P,Q,\text{car}\leq 351≤P,Q,car≤35

我把每個點都拆成兩個點 所有兩個點之間都給費用0 流量無限的邊表示這個點可以隨意經(jīng)過 限制費用為了限制采石頭的次數(shù) 如果這個點有可采集的那我就添加費用1 流量1的邊 否則不添加 然后跑最大費用最大流

我輸出方案的時候一定只有最大流個機器人可以到達 我就dfs即可 dfs 的時候針對一個機器人 我只需要找到一個可行路徑就可以 不需要把所有路徑完全搜索

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f #define N 3200 using namespace std; inline char gc(){static char now[1<<16],*S,*T;if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++; } inline int read(){int x=0;char ch=gc();while(ch<'0'||ch>'9') ch=gc();while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}return x; }bool flag[N]; int car,p,q,num=1,dx[]={0,1},dy[]={1,0},T,f[N],path[N],pre[N],h[N],id[40][40],mp[40][40],tot,nn; struct node{int y,next,z,c; }data[N*N]; inline void insert1(int x,int y,int z,int c){data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].c=c;data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].c=-c; } inline bool spfa(){queue<int>q;memset(f,128,sizeof(f));memset(flag,0,sizeof(flag));memset(pre,-1,sizeof(pre));flag[0]=1;f[0]=0;q.push(0);while(!q.empty()){int x=q.front();q.pop();flag[x]=0;for (int i=h[x];i;i=data[i].next){int y=data[i].y,z=data[i].z,c=data[i].c;if (f[x]+c>f[y]&&z){f[y]=f[x]+c;pre[y]=x;path[y]=i;if (!flag[y]) flag[y]=1,q.push(y);}}}if (pre[T]==-1) return 0;else return 1; } inline void dfs(int id,int x){if (x==tot) return;for (int i=h[x+nn];i;i=data[i].next){if(i&1||!data[i^1].z) continue;int y=data[i].y;if (x%p==y%p) printf("%d 0\n",id);else printf("%d 1\n",id);data[i].z+=1;data[i^1].z-=1;dfs(id,y);return;} } int main(){freopen("loj.in","r",stdin);car=read();p=read();q=read();tot=0;nn=p*q;T=nn<<1;for (int i=1;i<=q;++i)for(int j=1;j<=p;++j) id[i][j]=++tot,mp[i][j]=read();for (int i=1;i<=q;++i){for (int j=1;j<=p;++j){if (mp[i][j]==1) continue;insert1(id[i][j],id[i][j]+nn,inf,0);if (mp[i][j]==2) insert1(id[i][j],id[i][j]+nn,1,1);for (int k=0;k<2;++k){int x1=i+dx[k],y1=j+dy[k];if (x1>q||y1>p||mp[x1][y1]==1) continue;insert1(id[i][j]+nn,id[x1][y1],inf,0);}}}insert1(0,1,car,0);int ans=0; // for (int i=2;i<=num;++i) printf("%d %d %d\n",data[i].y,data[i].z,data[i].c);while(spfa()){int minn=inf,now=T;while(now) minn=min(minn,data[path[now]].z),now=pre[now];now=T;ans+=minn;while(now) {data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];}}//printf("%d\n",ans);for (int i=1;i<=ans;++i) dfs(i,1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的loj6225「网络流 24 题」火星探险问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。