洛谷P3356 火星探险问题(费用流)
2018-06-17 21:02:42来源:未知 阅读 ()
题目描述
火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。
用一个 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 表示向东移动。
输入输出样例
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
说明
车数,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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash