首页 > ACM题库 > HDU-杭电 > HDU 2922-Relax! It’s just a game-最短路径-[解题报告]HOJ
2014
02-23

HDU 2922-Relax! It’s just a game-最短路径-[解题报告]HOJ

Relax! It’s just a game

问题描述 :

You: What’s the score? Did I miss much?

Me: It’s 2-1 for elAhli and the second half just started. The first half was quite boring.

You: Who scored first? elAhli or ezZamalek?

Me: What difference does it make?

You: Big difference! I can predict the outcome of the match if I knew the order of which goals were scored in the first half.

Me: What do you mean?

You: It’s 2-1 for elAhli, right? One of three things could have happened: elAhli scored two goals then ezZamalek scored; Or, elAhli scored its first goal, then ezZamalek, then elAhli again; Or, ezZamalek scored first, then elAhli scored its two goals.

Me: So?!! I still don’t understand what difference does that make? It’s still 2-1 for elAhli! Why don’t you just relax and let us continue watching the game in peace.

You: You don’t understand!! I believe the probability of who’ll win depends on the order of how goals were scored. Now I have to predict the outcome for 3 possibilities.

Me: And what if the score was 3-2? What would you have done then?

You: I would have to work for 5 different possibilities. No?

Me: Of course not! The number of possibilities isn’t always equal to the sum.

You: Can you tell me when will it be equal to the sum?

Me: You’re a programmer, why don’t you write a program that counts the number of possibilities and compare it to the sum?

You: I don’t have the time, I want to watch the match. Besides, I have nine other problems to worry about.

Me: I’ll give you a hint. The possibilities will be equal to the sum only if one of the teams scored a certain number of goals.

输入:

Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B ) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1′s (which is not part of the test cases.)

输出:

Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B ) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1′s (which is not part of the test cases.)

样例输入:

2 1
1 0
-1 -1

样例输出:

2+1=3
1+0=1

很经典的一道题,借照了学长的做法(http://www.cnblogs.com/kane0526/archive/2012/12/14/2818747.html)

解题思路:

要判断从1出发,只经过给定的hotel且每两点间的路径满足小于ten hours.判断是否可以走到n点.

1<n<10^5 显然直接单源最短路径的djkstra会爆内存,只能用SPFA了.

对那些旅馆所表示的点map映射,在这些点间求最短路:

用SPFA分别求出各hotel(+起始点)到(其他hotel以及2个源点)的最短路径。小于ten hours则说明可以到达,时间置为1.

奇怪的WA:没想通为什么加了终点进去SPFA会挂,双向边从起点到终点和终点到起点应该是等价的。╮(╯﹏╰)╭

改成单向边表示同挂还有如果把底下的g[][]赋值改为双向赋值,还是会挂。-_-#奇怪的单双向。。。

在SPFA出各hotel的最短路径之后,对这些点用floyd算法求出g[start][end]即可。

#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
using namespace std;
#define inf 9999999
const int maxn=10000+5;
const int maxm=100+10;
struct Node
{
    int to,val;
    Node(int x,int y):to(x),val(y){}
};
int g[maxm][maxm],st[maxm],dist[maxn],que[maxn];
bool mark[maxn];
map<int,int>Map;
vector<Node>edge[maxn];
int n,h;
void SPFA(int v)
{
    for(int i=1; i<=n; i++) dist[i]=inf,mark[i]=0;
    dist[v]=0;
    int front=0,back=0;
    que[back++]=v;
    mark[v]=true;
    while(front!=back)
    {
        int u=que[front++];
        if(front==maxn) front=0;
        mark[u]=false;
        for(int i=0; i<edge[u].size(); i++)
        {
            int to=edge[u][i].to;
            int val=edge[u][i].val;
            if(dist[to]>dist[u]+val)
            {
                dist[to]=dist[u]+val;
                if(!mark[to])
                {
                    mark[to]=true;
                    que[back++]=to;
                    if(back==maxn) back=0;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
        if(dist[i]<=600)
            g[Map[v]][Map[i]]=1;
}
void floyd()
{
    for(int k=0; k<=h+1; k++)
        for(int i=0; i<=h+1; i++)
            for(int j=0; j<=h+1; j++)
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        Map.clear();
        for(int i=1; i<=n; i++) edge[i].clear();
        scanf("%d",&h);
        for(int i=1; i<=h; i++)
        {
            scanf("%d",&st[i]);
            Map[st[i]]=i;
        }
        st[0]=1;st[h+1]=n;
        Map[1]=0;Map[n]=h+1;
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            edge[u].push_back(Node(v,w));
        }
        for(int i=0; i<=105; i++)
            for(int j=0; j<=105; j++)
                if(i!=j) g[i][j]=inf;
                else g[i][j]=0;
        for(int i=1; i<=h; i++)
            SPFA(st[i]);
        floyd();
        if(g[0][h+1]==inf) printf("-1\n");
        else printf("%d\n",g[0][h+1]-1);
    }
    return 0;
}




解题参考:http://blog.csdn.net/z690933166/article/details/8932568


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.