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.

27
@00100000000000102000000000
@00100000000000102111000000
000010000000011002110000000
@00011110000100002111000000
000000000011100002000000000
3
@10
@00
@00
000
000
12
024841026058
@03990540049
@01108404608
030789005500
@95750159143
0

13
1
101

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;
}

您可能對以下文章有興趣

[UVA][Math] 920 - Sunny Mountains

[UVA][Math] 12444 - Bits and Pieces

[UVA] 10970 - Big Chocolate

[UVA][maxflow、黑白染色] 10349 - Antenna Placement