題目描述 火星探險隊的登陸艙將在火星錶面著陸，登陸艙內有多部障礙物探測車。登陸艙著陸後，探測車將離開登陸艙向先期到達的傳送器方向移動。探測車在移動中還必須採集岩石標本。每一塊岩石標本由最先遇到它的探測車完成採集。每塊岩石標本只能被採集一次。岩石標本被採集後，其他探測車可以從原來岩石標本所在處通過。探 ...
題目描述
火星探險隊的登陸艙將在火星錶面著陸，登陸艙內有多部障礙物探測車。登陸艙著陸後，探測車將離開登陸艙向先期到達的傳送器方向移動。探測車在移動中還必須採集岩石標本。每一塊岩石標本由最先遇到它的探測車完成採集。每塊岩石標本只能被採集一次。岩石標本被採集後，其他探測車可以從原來岩石標本所在處通過。探測車不能通過有障礙的地面。本題限定探測車只能從登陸處沿著向南或向東的方向朝傳送器移動，而且多個探測車可以在同一時間占據同一位置。如果某個探測車在到達傳送器以前不能繼續前進，則該車所採集的岩石標本將全部損失。
用一個 P·Q 網格表示登陸艙與傳送器之間的位置。登陸艙的位置在(X1,Y1)處，傳送器
的位置在(XP ,YQ)處。
X 1,Y 1 X 2 , Y 1 X 3 , Y 1 ... X P-1, Y 1 X P , Y 1
X 1,Y 2 X 2 , Y 2 X 3 , Y 2 ... X P-1, Y 2 X P , Y 2
X 1, Y 3 X 2 , Y 3 X 3 ,Y 3 ... X P-1, Y 3 X P , Y 3
... ...
X 1 ,Y Q-1 X 2 , Y Q-1 X 3 , Y Q-1 ... X P-1, Y Q-1 X P , Y Q-1
X 1,Y Q X 2 , Y Q X 3 , Y Q ... X P-1, Y Q X P ,Y Q
給定每個位置的狀態，計算探測車的最優移動方案，使到達傳送器的探測車的數量最多，
而且探測車採集到的岩石標本的數量最多
輸入輸出格式
輸入格式：
第 1行為探測車數，第 2 行為 P 的值，第3 行為Q 的值。接下來的 Q 行是表示登陸艙與傳送器之間的位置狀態的 P·Q 網格。用 3 個數字表示火星錶面位置的狀態：0 表示平坦無障礙，1表示障礙，2 表示石塊。
輸出格式：
每行包含探測車號和一個移動方向，0 表示向南移動，1 表示向東移動。
輸入輸出樣例
輸入樣例#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 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
說明
車數,P,Q<=35
這題與深海機器人問題
不過也有不同
首先此問題是點權，因此我們考慮拆點
另外這題需要輸出方案
我們考慮利用發現邊的性質：反向邊有多少流量，就代表這個點被經過了多少次
因此我們可以利用反向邊來統計出該點的經過次數
然後枚舉每一個車，讓其沿邊走就好
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> #include<cmath> #define AddEdge(x,y,z,f) add_edge(x,y,z,f),add_edge(y,x,-z,0) using namespace std; const int MAXN=1e5+10; const int INF=1e8+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int N,M,K,S,T; int anscost=0; struct node { int u,v,w,f,nxt; }edge[MAXN]; int head[MAXN],num=2; inline void add_edge(int x,int y,int z,int f) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].f=f; edge[num].nxt=head[x]; head[x]=num++; } int Pre[MAXN],vis[MAXN],dis[MAXN]; bool SPFA() { queue<int>q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[S]=0; q.push(S); while(q.size()!=0) { int p=q.front();q.pop(); vis[p]=0; for(int i=head[p];i!=-1;i=edge[i].nxt) { if(dis[edge[i].v]>dis[p]+edge[i].w&&edge[i].f) { dis[edge[i].v]=dis[p]+edge[i].w; Pre[edge[i].v]=i; if(!vis[edge[i].v]) vis[edge[i].v]=1,q.push(edge[i].v); } } } return dis[T]<=INF; } void f() { int nowflow=INF; for(int now=T;now!=S;now=edge[Pre[now]].u) nowflow=min(nowflow,edge[Pre[now]].f); for(int now=T;now!=S;now=edge[Pre[now]].u) edge[Pre[now]].f-=nowflow, edge[Pre[now]^1].f+=nowflow; anscost+=nowflow*dis[T]; } void MCMF() { int ans=0; while(SPFA()) f(); } int point=0; int belong[1001][1001],can[1001][1001]; main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); K=read(); M=read();N=read(); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) belong[i][j]=++point; for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) { int opt=read(); if(opt==2) AddEdge(belong[i][j],belong[i][j]+point,-1,1); if(opt!=1) AddEdge(belong[i][j],belong[i][j]+point,0,INF); if(i<N) AddEdge(belong[i][j]+point,belong[i+1][j],0,INF); if(j<M) AddEdge(belong[i][j]+point,belong[i][j+1],0,INF); } S=0;T=point*4; AddEdge(S,belong[1][1],0,K); AddEdge(belong[N][M]+point,T,0,K); MCMF(); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) for(int k=head[belong[i][j]];k!=-1;k=edge[k].nxt) if(edge[k].v==belong[i][j]+point) can[i][j]+=edge[k^1].f; for(int kk=1;kk<=K;kk++) { int xx=1,yy=1; while(xx!=N||yy!=M) { if(can[xx+1][yy]) printf("%d 0\n",kk),can[xx][yy]--,xx++; else printf("%d 1\n",kk),can[xx][yy]--,yy++; } } return 0; }
