Rockdu's Blog

题目描述

火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。

用一个 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

考虑和方格取数一样，我们把一个方格下点拆成两个点。对于非障碍点，中间连一条费用为0流量为INF的边（可以走这里过但是不取走东西）。对于有石子的点，我们再连一条费用为1流量为1的边（只能取走一次）。注意费用流不能叠加，有石子的点既有非障碍点的连边又有自己的连边。把起点中间那条边的流量设为星球车的台数，跑最大费用流即可。

对于输出方案，我们记录每一个方格下点对应的中间边的反向边（快速获得该边增流的流量）。每一次在方格图上DFS，如果该点还有增流流量我们就走上去并且把该点增流流量减一。走K次就好了。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxm = 100005, maxn = 105, maxp = maxn * maxn;
const int IN = 0, OUT = 1, inf = 0x3f3f3f3f;
int n, m, k;
struct edge {
	int v, cost, w, next;
}e[maxm << 1];
int head[maxp], cnt, pos[maxn][maxn][2], mp[maxn][maxn], pcnt;
int st, ed, nxt[maxn][maxn][2], flow[maxn][maxn];

void adde(const int &u, const int &v, const int &w, const int &cost) {
	e[++cnt] = (edge) {v, cost, w, head[u]};
	head[u] = cnt;
	e[++cnt] = (edge) {u, -cost, 0, head[v]};
	head[v] = cnt;
}

int dis[maxp], vis[maxp], fa[maxp], eid[maxp], ans;
void SPFA(int s, int t) {
	queue<int > q;
	for(register int i = 0; i <= pcnt; ++i) dis[i] = -inf;
	memset(vis, 0, sizeof(vis));
	memset(fa, 0, sizeof(fa));
	q.push(s), dis[s] = 0, vis[s] = 1;
	while(!q.empty()) {
		int u = q.front();
		q.pop(), vis[u] = 0;
		for(register int i = head[u]; i; i = e[i].next) {
			if(!e[i].w) continue;
			int v = e[i].v;
			if(dis[v] < dis[u] + e[i].cost) {
				dis[v] = dis[u] + e[i].cost;
				fa[v] = u, eid[v] = i;
				if(vis[v]) continue;
				q.push(v), vis[v] = 1;
			}
		}
	}
}

void ExtFlow(int s, int v, int & mn) {
	if(v == s) return;
	mn = min(e[eid[v]].w, mn);
	ExtFlow(s, fa[v], mn);
	e[eid[v]].w -= mn;
	e[eid[v] ^ 1].w += mn;
	ans += e[eid[v]].cost * mn;
}

int GetAns(int s, int t) {
	int mn = inf;
	while(1) {
		SPFA(s, t);
		if(dis[t] == -inf) break;
		mn = inf, ExtFlow(s, t, mn);
	}
	return ans;
}

void print(int x, int y, int id) {
	--flow[x][y];
	if(x + 1 <= n && flow[x + 1][y]) printf("%d %d\n", id, 0), print(x + 1, y, id);
	else if(y + 1 <= m && flow[x][y + 1]) printf("%d %d\n", id, 1), print(x, y + 1, id);
}

int main() {
	scanf("%d%d%d", &k, &m, &n);
	cnt = 1;
	for(register int i = 1; i <= n; ++i)
		for(register int j = 1; j <= m; ++j) {
			scanf("%d", &mp[i][j]);
			pos[i][j][IN] = ++pcnt; 
			pos[i][j][OUT] = ++pcnt;
			if(i == 1 && j == 1) continue;
			if(mp[i][j] == 1) continue;
			adde(pos[i][j][IN], pos[i][j][OUT], inf, 0), nxt[i][j][0] = cnt;
			if(mp[i][j] == 2) 
				adde(pos[i][j][IN], pos[i][j][OUT], 1, 1), nxt[i][j][1] = cnt;
		}
	for(register int i = 1; i < m; ++i) adde(pos[n][i][OUT], pos[n][i + 1][IN], inf, 0);
	for(register int i = 1; i < n; ++i) adde(pos[i][m][OUT], pos[i + 1][m][IN], inf, 0);
	for(register int i = 1; i < n; ++i)
		for(register int j = 1; j < m; ++j) {
			adde(pos[i][j][OUT], pos[i + 1][j][IN], inf, 0);
			adde(pos[i][j][OUT], pos[i][j + 1][IN], inf, 0);
		}
	if(mp[1][1] == 2) adde(pos[1][1][IN], pos[1][1][OUT], k - 1, 0), adde(pos[1][1][IN], pos[1][1][OUT], 1, 1);
	else adde(pos[1][1][IN], pos[1][1][OUT], k, 0);
	st = pos[1][1][IN], ed = pos[n][m][OUT];
	GetAns(st, ed);
	for(register int i = 1; i <= n; ++i)
		for(register int j = 1; j <= m; ++j) 
			flow[i][j] = e[nxt[i][j][0]].w + e[nxt[i][j][1]].w;
	for(register int i = 1; i <= k; ++i) 
		print(1, 1, i);
	return 0;
}