[题解] PowerOJ 1758 火星探险问题 (最大费用最大流)

- 传送门 -

　https://www.oj.swust.edu.cn/problem/show/1758

# 1758: 火星探险问题

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 50 Accepted: 6 Page View: 437

Description

火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。 «编程任务：用一个PxQ 网格表示登陆舱与传送器之间的位置。登陆舱的位置在(X1,Y1)处，传送器的位置在(XP ,YQ)处。给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多，而且探测车采集到的岩石标本的数量最多。

Input

由文件input.txt提供输入数据。文件的第1行为探测车数，第2 行为P的值，第3 行为 Q 的值。接下来的Q 行是表示登陆舱与传送器之间的位置状态的PxQ 网格。用3 个数字表示火星表面位置的状态：0 表示平坦无障碍，1表示障碍，2 表示石块。

Output

程序运行结束时，将每个探测车向传送器移动的序列输出到文件output.txt 中。每行包含探测车号和一个移动方向，0 表示向南移动，1 表示向东移动。

Sample Input
Raw
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
Sample Output
Raw

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

Hint

No SPJ support now!

Source

线性规划与网络流24题

- 题意 -

　对于 Q*P 网格, 如果格点内是 1 不能走, 2 表示一个价值为 1 的点, 0 没有特征.
　注意只有第一次到达 2 才能得到价值(如果有多条路径都经过这一点, 只取一次价值).
　现在求出 S(探测车数) 条从(1, 1)(左上) 到 (n, m)(右下) 的路径, 使得到价值最大, 输出每一条路径.
　0 表示向下走, 1 表示向右走.
　

- 思路 -

　建图什么的就先都连inf的可行边, 再对格点内为 2 的格子多连一条容量 1, 费用 1 的边.
　源点连(1, 1)容量为S, (n,m)连汇点容量为S.
　求最大费用最大流.
　
　重点在输出吧...
　我们只搜索反向边, 反向变 > 0 说明这条边是被经过的.
　因为拆了点, 所以我们固定一下拆出来的一个点集, 记录其内的点以便输出路径.
　
　细节见代码.
　
　PS:
　poweroj没有SPJ挂啦难过!!!
　但是没关系我有dalao写哒!!!
　

- 代码 -

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 4000;
const int M = 1e6;
const int inf = 0x3f3f3f3f;

int NXT[M], TO[M], V[M], CT[M];
int DIS[N], VIS[N], HD[N], PRE[N];
int MAP[40][40];
int ss, tt, n, m, p, sz, tot;
queue<int> q;

int mk(int i, int j, int z) {
	return z * tot + (i - 1) * m + j;
}

void add(int x, int y, int z, int c) {
	TO[sz] = y; V[sz] = z; CT[sz] = c;
	NXT[sz] = HD[x]; HD[x] = sz++;
	TO[sz] = x; V[sz] = 0; CT[sz] = -c;
	NXT[sz] = HD[y]; HD[y] = sz++;
}

bool spfa() {
	memset(DIS, 0xc0, sizeof (DIS));
	DIS[ss] = 0;
	PRE[tt] = -1;
	q.push(ss);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		VIS[u] = 0;
		for (int i = HD[u]; i != -1; i = NXT[i]) {
			int v = TO[i];
			if (V[i] && DIS[v] < DIS[u] + CT[i]) {
				DIS[v] = DIS[u] + CT[i];
				PRE[v] = i;
				if (!VIS[v]) {
					VIS[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return PRE[tt] != -1;
}

void mcmf() {
	while (spfa()) {
		int tmp = inf;
		for (int i = tt; i != ss; i = TO[PRE[i]^1])
			if (tmp > V[PRE[i]]) tmp = V[PRE[i]];
		for (int i = tt; i != ss; i = TO[PRE[i]^1]) {
			V[PRE[i]] -= tmp;
			V[PRE[i]^1] += tmp;
		}
	}
}

void bfs(int p, int x, int pre) {
	if (x != 1 && x <= tot) { //记录x <= tot 的点来标记路径
		if (x == pre + m)
			printf("%d 0
", p);
		else
			printf("%d 1
", p);
		pre = x;
	}
	if (x == tot) return;
	for (int i = HD[x]; i != -1; i = NXT[i]) {
		if (V[i^1] && i % 2 == 0) { //只搜反向变
			bfs(p, TO[i], pre);
			V[i^1] --;
			break;
		}
	}
}

void print() {
	for (int i = 1; i <= p; ++i) {
		bfs(i, 1, 1);
	}
}

int main() {
	memset(HD, -1, sizeof (HD));
	scanf("%d%d%d", &p, &m, &n);
	tot = n * m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &MAP[i][j]);
	ss = 0, tt = n * m * 2 + 1;
	add(ss, mk(1, 1, 0), p, 0);
	add(mk(n, m, 1), tt, p, 0);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (MAP[i][j] == 1)
				continue;
			add(mk(i, j, 0), mk(i, j, 1), inf, 0);
			if (MAP[i][j] == 2)
				add(mk(i, j, 0), mk(i, j, 1), 1, 1);
			if (i != n && MAP[i + 1][j] != 1)
				add(mk(i, j, 1), mk(i + 1, j, 0), inf, 0);
			if (j != m && MAP[i][j + 1] != 1)
				add(mk(i, j, 1), mk(i, j + 1, 0), inf, 0);
		}
	}
	mcmf();
	print();
	return 0;
}