首页 > 搜索 > BFS搜索 > HDU 1601 Galactic Import-BFS-[解题报告] C++
2013
12-12

HDU 1601 Galactic Import-BFS-[解题报告] C++

Galactic Import

问题描述 :

With the introduction of the new ThrustoZoom gigadimensional drive, it has become possible for HyperCommodities, the import/export conglomerate from New Jersey, to begin trading with even the most remote galaxies in the universe. HyperCommodities wants to import goods from some of the galaxies in the Plural Z sector. Planets within these galaxies export valuable products and raw materials like vacuuseal, transparent aluminum, digraphite, and quantum steel. Preliminary reports have revealed the following facts:

Each galaxy contains at least one and at most 26 planets. Each planet within a galaxy is identified by a unique letter from A to Z.

Each planet specializes in the production and export of one good. Different planets within the same galaxy export different goods.

Some pairs of planets are connected by hyperspace shipping lines. If planets A and B are connected, they can trade goods freely. If planet C is connected to B but not to A, then A and C can still trade goods with each other through B, but B keeps 5% of the shipment as a shipping fee. (Thus A only receives 95% of what C shipped, and C receives only 95% of what A shipped.) In general, any two planets can trade goods as long as they are connected by some set of shipping lines, but each intermediate planet along the shipping route keeps 5% of what it shipped (which is not necessarily equal to 5% of the original shipment).

At least one planet in each galaxy is willing to open a ThrustoZoom shipping line to Earth. A ThrustoZoom line is the same as any other shipping line within the galaxy, as far as business is concerned. For example, if planet K opens a ThrustoZoom line to Earth, then the Earth can trade goods freely with K, or it can trade goods with any planet connected to K, subject to the usual shipping fees.

HyperCommodities has assigned a relative value (a positive real number less than 10) to each planet’s chief export. The higher the number, the more valuable the product. More valuable products can be resold with a higher profit margin in domestic markets. The problem is to determine which planet has the most valuable export when shipping fees are taken into account.

输入:

The input consists of one or more galaxy descriptions. Each galaxy description begins with a line containing an integer N which specifies the number of planets in the galaxy. The next N lines contain descriptions of each planet, which consist of:

1) The letter used to represent the planet.

2) A space.

3) The relative value of the planet’s export, in the form d.dd.

4) A space.

5) A string containing letters and/or the character `*’; a letter indicates a shipping line to that planet, and a `*’ indicates a willingness to open a ThrustoZoom shipping line to Earth.

输出:

For each galaxy description, output a single line which reads "Import from P" where P is the letter of the planet with the most valuable export, once shipping fees have been taken into account. (If more than one planet have the same most valuable export value then output the plant which is alphabetically first).

样例输入:

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

样例输出:

Import from F
Import from A
Import from A

被归在最短路径下面,其实完全可以用bfs解决,要说bfs也算是dijkstra的一种特殊情况吧。

 

这道题的最大的难度不是解决问题的过程,而是读题的过程,题意叙述可够难为人的,英文啊英文。。。

 

星球间运送货物(双向的),每个星球都有独特的资源。如果不能直接到达的话中间星球要收取费用5%,问运送到地球可以达到最大价值的是从哪个星球运送的,不要管那个星号“*”所描述的乱七八糟的东西,就是星球与地球有直接的连接。单终点最短路径转化为单源最短路径(当然若果你不用bfs的话)。

 

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int main(void)
{
    int n;
    char c;
    int k,t,e,mark;
    int i,j,from,to;
    int dist[27];
    int mat[27][27];
    double max,value[27];
    queue<int> q;
    while( cin >> n )
    {
        getchar();
        for( i = 0; i <= 26; i++ )
            for( j = 0; j <= 26; j++ )
                mat[i][j] = 0;
        for( i = 0; i <= 26; i++ )
            dist[i] = value[i] = 0;  //以上为初始化
            
        for( i = 1; i <= n; i++ )
        {
            c = getchar();
            from = c - 'A';
            cin >> value[from];
            getchar();
            while( (c=getchar()) != '/n')
            {
                if( c == '*')  to = 26;
                else to = c- 'A';
                mat[from][to] = mat[to][from] = 1; 
            }
        }        //以上为图的输入过程
        dist[26] = 1;
        q.push(26);
        while( !q.empty() )
        {
            e = q.front();
            q.pop();
            for( j = 0; j < 26; j++)
            {
                k = mat[e][j];
                if( k == 1 && dist[j] == 0)
                {
                    dist[j] = dist[e] + 1;
                    q.push(j);
                }
            }
        }               //以上为bfs的过程 
        
        for( i = 0,max = -1; i < 26; i++ )
        {
            if( dist[i] > 2 )
            {
                t = dist[i] - 2;
                while( t--)
                    value[i] *= 0.95;
            } 
            else if( dist[i] != 2)
                value[i] = 0;
           
            if( value[i] > max )
                max = value[mark = i];
        }      
        cout << "Import from " << (char)(mark+'A') << endl;
        
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/dangwenliang/article/details/5797289


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢