首页 > ACM题库 > HDU-杭电 > hdu 1970 Ticket to Ride-动态规划-[解题报告]C++
2013
12-26

hdu 1970 Ticket to Ride-动态规划-[解题报告]C++

Ticket to Ride

问题描述 :

Ticket to Ride is a board game for up to 5 players. The goal of the game is to set up train lines (and to thwart the opponents’ attempts at setting up their train lines). At the beginning of play, each player is assigned four train lines. A player may choose to discard as many of these four assignments as she likes. Each assignment has a score, corresponding to its difficulty (so, typically, a train line between e.g. Stockholm and Tokyo would be worth more than a train line between e.g. Stockholm and Utrecht). At the end of the game, each player gets points for the assignments that they have successfully completed, and penalty points for the assignments that they have failed to complete.

An assignment consists of a pair of cities that are to be connected by a series of shorter railway routes. A route can be claimed (for a certain cost associated with the route), but things are complicated by the fact that there is only a limited number of routes, and once a player claims a route, none of the other players can claim it. A player has successfully set up a train line between two cities if there is a path between the two cities using only routes that have been claimed by this player. For simplicity, we will ignore all additional aspects of the game (including the actual process of claiming routes and additional ways to score points).

For instance, if your assignment is to connect Stockholm and Amsterdam in the Figure above, you would probably want to claim the routes between Stockholm and Copenhagen, and between Copenhagen and Amsterdam. But if another player manages to claim the route between Copenhagen and Stockholm before you, your train line would have to use some other routes, e.g. by going to Copenhagen via Oslo.

In this problem, we will consider the rather bold strategy of trying to complete all four assignments (typically, this will be quite hard). As a preliminary assessment of the difficulty of achieving this, we would like to calculate the minimum cost of setting up all four lines assuming that none of the other players interfere with our plans. Your job is to write a program to determine this minimum cost.

输入:

The input consists of several (at most 20) games to be analyzed. Each game starts with two integers 1 <= n <= 30, 0 <= m <= 1 000, giving the number of cities and railway routes in the map, respectively. Then follow n lines, giving the names of the n cities. City names are at most 20 characters long and consist solely of lower case letters (’a’-’z’).

After this follow m lines, each containing the names of two different cities and an integer 1 <= c <= 10 000, indicating that there is a railway route with cost c between the two cities. Note that there may be several railway routes between the same pair of cities. You may assume that it is always possible to set up a train line from any city to any other city.

Finally, there will be four lines, each containing the names of two cities, giving the four train line assignments.

The input is terminated by a case where n = m = 0. This case should not be processed.

输出:

The input consists of several (at most 20) games to be analyzed. Each game starts with two integers 1 <= n <= 30, 0 <= m <= 1 000, giving the number of cities and railway routes in the map, respectively. Then follow n lines, giving the names of the n cities. City names are at most 20 characters long and consist solely of lower case letters (’a’-’z’).

After this follow m lines, each containing the names of two different cities and an integer 1 <= c <= 10 000, indicating that there is a railway route with cost c between the two cities. Note that there may be several railway routes between the same pair of cities. You may assume that it is always possible to set up a train line from any city to any other city.

Finally, there will be four lines, each containing the names of two cities, giving the four train line assignments.

The input is terminated by a case where n = m = 0. This case should not be processed.

样例输入:

10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki
2 1
first
second
first second 10
first first
first first
second first
first first
0 0

样例输出:

3907
10

题目传送门:http://poj.org/problem?id=3123

题目大意是:

给出一个无向图,和四对数据。每对数据分别为图中的两个点。

要求添加一些边,使每对点都能连通,让总边权最小。



首先考虑一个子问题:指定一些点,添加一些边,让它们连通,并且总边权最小。

这个问题就是Minimal Steiner Tree(最小斯坦纳树)问题,什么是Minimal Steiner Tree 见这里


Minimal Steiner Tree是一个NP问题,但可以转成DP来求解。

动归的转移方程:

dp[mask][i],其中是以j为根,包含mask中的点的最小生成树的权值。

mask是点的集合,可以用二进制进行状态压缩。


在得知dp[mask - 1][1...N]的情况下,如何推出dp[mask][1...N]呢?

两个步骤实现:

step1推出:

a = min{dp[m1][i] + dp[m2][i]},其中m1 | m2 = mask。

这个很好理解…..就是两个互补子集…..

在计算子集的时候,可有用for(int sub = mask; sum; sum = (sum – 1) & mask)来枚举子集,我用了这个优化比以前快了将近一倍的速度(果断63MS,杀进POJ第一页)。

step2推出

b = min(dp[mask][j] + d[j][i])

这个更好理解了….就是加上一个边….让i成为了根…..


程序中,每次都从dp[mask][1...N]中选出最小的一个dp[mask][c],按这种顺序更新就能保证结果的正确

因此dp[mask][i] = min(a, b)


代码:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
    int INF = 99999999, N, K, d[30][30], i, j, k, x, y, z;
    int dp[256][30], e[8], v[30], c, b;
    string s, t;
    while (cin >> N >> K && N)
    {
        map <string, int> cityMap;
        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                d[i][j] = i == j ? 0 : INF;
        for (i = 0; i < N; i++)
        {
            cin >> s;
            cityMap[s] = i;
        }
        if (K)
            while (cin >> s >> t >> z, x = cityMap[s],
                    y = cityMap[t],
                    d[x][y] = d[y][x] = min(d[y][x], z), --K);
        for (k = 0; k < N; k++)
            for (i = 0; i < N; i++)
                for (j = 0; j < N; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        for (i = 0; i < 8; i++)
        {
            cin >> s;
            e[i] = cityMap[s];
            for (j = 0; j < N; j++)
                dp[1 << i][j] = d[j][e[i]];
        }
        for (i = 1; i < 256; i++)
        {
            if (!(i & (i - 1)))
                continue;
            // step1
            for (k = 0; k < N; k++)
            {
                dp[i][k] = INF;
                v[k] = 0;
                /*for (j = 1; j < i; j++)
                    if ((i | j) == i)
                        dp[i][k] = min(dp[i][k], dp[j][k] + dp[i-j][k]);*/
                for (int sub = i; sub; sub = (sub - 1) & i)
                {
                    dp[i][k] = min(dp[i][k], dp[sub][k] + dp[i - sub][k]);
                }
            }
            // step2
            for (j = 0; b = INF, j < N; j++)
            {
                for (k = 0; k < N; k++)
                    if (dp[i][k] <= b && !v[k])
                        b = dp[i][c = k];
                for (k = 0, v[c] = 1; k < N; k++)
                    dp[i][c] = min(dp[i][c], dp[i][k] + d[k][c]);
            }
        }

        // step3
        for (i = 0, b = INF; z = 0, i < 256; b = min(b, z), i++)
            for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
                for (k = 0; k < 8; k += 2)
                    if ((i >> k & 3) == j)
                        y += 3 << k, x = e[k];

        cout << b << endl;
    }
    return 0;
}

解题转自:http://blog.csdn.net/lvlawliet/article/details/6958030


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?