首页 > ACM题库 > HDU-杭电 > HDU 1460 Beggar My Neighbour-Dijkstra-[解题报告] C++
2013
12-11

HDU 1460 Beggar My Neighbour-Dijkstra-[解题报告] C++

Beggar My Neighbour

问题描述 :

"Beggar My Neighbour” (sometimes known as "Strip Jack Naked”) is a traditional card game, designed to help teach beginners something about cards and their values. A standard deck is shuffled and dealt face down to the two players, the first card to the non-dealer, the second to the dealer, and so on until each player has 26 cards. The dealer receives the last card. The non-dealer starts the game by playing the top card of her deck (the second last card dealt) face up on the table. The dealer then covers it by playing her top card face up. Play continues in this fashion until a “face” card (Ace, King, Queen or Jack) is played. The next player must then “cover” that card, by playing one card for a Jack, two for a Queen, three for a King and four for an Ace. If a face card is played at any stage during this sequence, play switches and the other player must cover that card. When this sequence has ended, the player who exposed the last face card takes the entire heap, placing it face down under her existing deck. She then starts the next round by playing one card face up as before, and play continues until one player cannot play when called upon to do so, because they have no more cards.

Write a program that will simulate playing this game. Remember that a standard deck (or pack) of cards contains 52 cards. These are divided into 4 suits – Spades, Hearts, Diamonds and Clubs. Within each suit there are 13 cards – Ace (A), 2-9, Ten (T), Jack (J), Queen (Q) and King (K).

输入:

Input will consist of a series of decks of cards. Each deck will give the cards in order as they would be dealt (that is in the example deck below, the non-dealer would start the game by playing the H2). Decks will occupy 4 lines with 13 cards on each. The designation of each card will be the suit (S, H, D, C) followed by the rank (A, 2-9, T, J, Q, K). There will be exactly one space between cards. The file will be terminated by a line consisting of a single #.

输出:

Output will consist of a series of lines, one for each deck in the input. Each line will consist of the number of the winning player (1 is the dealer, 2 is the first to play) and the number of cards in the winner’s hand (ignoring any on the stack), right justified in a field of width 3.

样例输入:

HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
#

样例输出:

1 44

题意:给出了城市数n,以及街道数m(街道是双向均可通行的), 对于每一条街mi,给出它的两端的城市,以及所能承载的最大货物运输量。

要求输出,从城市1到城市n,最多能运输多少货物。

分析:无向、带权图的单源最短路问题。 但这里路径的定义变成了:这条路上权值最小的那段路 的权值(而非所有段的权值之和)。

我们的任务就是求出:每一条从1到n的路上,“路径” 的最大值。 这样,就成了求单源最长“路径”。

//hoj 1653
//Dijkstra 单源最短路
//注意此题中路长的定义变成了,各段路的权值的最小值

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <climits>
#define N 1005
#define MinN 0
using namespace std;

int map[N][N];

bool used[N];
int dis[N];
int main()
{
    int caseNum;
    scanf("%d",&caseNum);
    for(int t=1; t<=caseNum; t++) {

        memset(map,0,sizeof(map));  //初始化为零,是因为不相邻的两个点间的通货能力为0(不要惯性思维初始化为无穷大)
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=0; i<m; i++) {
            int s,e;
            scanf("%d %d",&s,&e);
            scanf("%d",&map[s][e]);
            map[e][s]=map[s][e];

        }

        memset(used,0,sizeof(used));

        for(int i=1; i<=n; i++) {
            dis[i]=map[1][i];        //dis[i]储存点i到源点1的路径
        }

        used[1]=1;
        int count=n;

        while(count--) {
            int m=MinN;
            int v;
            for(int i=2; i<=n; i++) {
                if(!used[i]&&m<dis[i]) {  //找到与源点1通货能力最大的,且尚未访问过的点。这是一种贪心的思想。
                    m=dis[i];
                    v=i;
                }
            }
            used[v]=1;
            for(int j=1; j<=n; j++) {
                dis[j]=max(dis[j],min(dis[v],map[v][j])); //转移方程
                //min(dis[v],map[v][j])获得的是从1到v再到j这条路的“路径”。
                //max()用来更新点1到点j的最长路径。这条路可能是从1直接到j,也可能是从1到v再到j      
            }
            printf("Scenario #%d:\n",t);
            printf("%d\n\n",dis[n]);
        }
        return 0;
    }

解题报告转自:http://blog.csdn.net/zhuang19922011/article/details/8034990


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。