POJ: Evacuation Plan

3 4
-3 3 5
-2 -2 6
2 2 5
-1 1 3
1 1 4
-2 -2 7
0 -1 3
3 1 1 0
0 0 6 0
0 3 0 2
SUBOPTIMAL
3 0 1 1
0 0 6 0
0 4 0 1
#include <cstdio>
#include <vector>
using namespace std;#define MAX_N 100
#define MAX_M 100
#define MAX_V ((MAX_N) + (MAX_M) + 1)
#define INF 0x3f3f3f3f
int g[MAX_V][MAX_V];
int pre[MAX_V][MAX_V];
bool used[MAX_V];
int e[MAX_N][MAX_M];
int x[MAX_N];
int y[MAX_N];
int b[MAX_N];
int p[MAX_M];
int q[MAX_M];
int c[MAX_M];
int main(int argc, char *argv[]) {
int N, M;
scanf("%d%d", &N, &M);
int V = M + N + 1;
for (int i = 0; i < V; ++i) fill(g[i], g[i] + V, INF);
for (int i = 0; i < N; ++i) {
getchar();
scanf("%d%d%d", &x[i], &y[i], &b[i]);
}
for (int i = 0; i < M; ++i) {
getchar();
scanf("%d%d%d", &p[i], &q[i], &c[i]);
}
for (int i = 0; i < N; ++i) {
getchar();
for (int j = 0; j < M; ++j) {
scanf("%d", &e[i][j]);
}
}
for (int j = 0; j < M; ++j) {
int sum = 0;
for (int i = 0; i < N; ++i) {
int c = abs(x[i] - p[j]) + abs(y[i] - q[j]) + 1;
g[i][N + j] = c;
if (e[i][j] > 0) g[N + j][i] = -c;
sum += e[i][j];
}
if (sum > 0) g[N+M][N+j] = 0;
if (sum < c[j]) g[N+j][N+M] = 0;
}
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) pre[i][j] = i;
}
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (g[i][j] > g[i][k] + g[k][j]) {
g[i][j] = g[i][k] + g[k][j];
pre[i][j] = pre[k][j];
if (i == j && g[i][i] < 0) {
fill(used, used + V, false);
for (int v = i; !used[v]; v = pre[i][v]) {
used[v] = true;
if (v != N + M && pre[i][v] != N + M) {
if (v >= N) e[pre[i][v]][v - N]++;
else e[v][pre[i][v] - N]--;
}
}
printf("SUBOPTIMAL\n");
for (int x = 0; x < N; ++x) {
for (int y = 0; y < M; ++y) {
printf("%d%c", e[x][y], (y == M - 1) ? '\n' : ' ');
}
}
return 0;
}
}
}
}
}
printf("OPTIMAL\n"); return 0;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store