[UVA][最少費用流] 11301 - Great Wall of China
G. Great Wall of China
Time Limit: 6 sec
|
Description
The alfalfas team is visiting the Great Wall of China. They want to cross it from beginning to the end, but some parts of the Great Wall was rebuilt for the tourists and it is necessary to pay a toll. Then, they bought a map that represented the Great Wall as a grid of 5 rows and n columns. Each site was marked with a digit that represents the cost to the toll. The alfalfas want that you write a program to get the way to cross the Great Wall from column 0 to n - 1 with the minimum cost. They began in the first column, each per represented by '@'. The cost of all sites in the first column are 0.They can move only horizontally and vertically. They want to visit all unique parts of the Great wall, so they never pass through the sites that another alfalfa has visited.
The Input
For each test case the first line contain an integer n (3 ≤ n ≤ 1000). In the follow 5 lines contain n characters, each character would be indicate the toll of this site and in the first columns the characters would be 0, or '@' that indicate the position of an alfalfa, there must be always be three '@'.
The Output
For each test c
ase you must print the minimum price that the alfalfas need to pay for their travel.
|
|
Problemsetter: Rodrigo Burgos Domínguez
題目描述：
一開始有一些導遊帶領參觀萬里長城，每名導遊一開始都在地圖的左側 '@' 表示。
而有些地方必須收費，在不彼此碰到面的情況下，必須將所有人送到最右側。
題目解法：
建造一個最少費用流的模型。
由於不能重複走點，必須將盤面上的每一個點拆成進和出兩點，而其中間容量為 1 花費為 0。
使用 SPFA 的 LLL 策略會快上很多。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
int x, y, cap, cost;// x->y, v
int next;
} edge[1000005];
int e, head[10005], dis[10005], prev[10005], record[10005], inq[10005];
void addEdge(int x, int y, int cap, int cost) {
edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t) {
int mncost = 0, flow, totflow = 0;
int i, x, y;
while(1) {
memset(dis, 63, sizeof(dis));
int oo = dis[0];
dis[s] = 0;
deque<int> Q;
Q.push_front(s);
while(!Q.empty()) {
x = Q.front(), Q.pop_front();
inq[x] = 0;
for(i = head[x]; i != -1; i = edge[i].next) {
y = edge[i].y;
if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
dis[y] = dis[x] + edge[i].cost;
prev[y] = x, record[y] = i;
if(inq[y] == 0) {
inq[y] = 1;
if(Q.size() && dis[Q.front()] > dis[y])
Q.push_front(y);
else
Q.push_back(y);
}
}
}
}
if(dis[t] == oo)
break;
flow = oo;
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
flow = min(flow, edge[ri].cap);
}
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
edge[ri].cap -= flow;
edge[ri^1].cap += flow;
edge[ri^1].cost = -edge[ri].cost;
}
totflow += flow;
mncost += dis[t] * flow;
}
return mncost;
}
int main() {
int n, m;
char s[5][1024];
int i, j, k;
while(scanf("%d", &n) == 1 && n) {
e = 0;
memset(head, -1, sizeof(head));
for(i = 0; i < 5; i++)
scanf("%s", s[i]);
int st = (2*5*n), ed = st+1;
for(i = 0; i < 5; i++) {
if(s[i][0] == '@') {
addEdge(st, (i*n+0)*2, 1, 0);
}
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
for(i = 0; i < 5; i++) {
for(j = 0; j < n; j++) {
int node = (i*n+j)*2+1;//out node
for(k = 0; k < 4; k++) {
int tx = i+dx[k], ty = j+dy[k];
if(tx < 0 || ty < 0 || tx >= 5 || ty >= n)
continue;
if(s[tx][ty] == '@')
continue;
addEdge(node, (tx*n+ty)*2, 1, s[tx][ty]-'0');
}
addEdge(node-1, node, 1, 0);
}
}
for(i = 0; i < 5; i++) {
int node = (i*n+(n-1))*2+1;//out node.
addEdge(node, ed, 1, 0);
}
printf("%d\n", mincost(st, ed));
}
return 0;
}