HDU 1224 Free DIY Tour

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1224

题目:

Free DIY Tour
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1894    Accepted Submission(s): 619

Problem Description
Weiwei is a software engineer of ShiningSoft. He has just excellently fulfilled a software project with his fellow workers. His boss is so satisfied with their job that he decide to provide them a free tour around the world. It's a good chance to relax themselves. To most of them, it's the first time to go abroad so they decide to make a collective tour.

The tour company shows them a new kind of tour circuit - DIY circuit. Each circuit contains some cities which can be selected by tourists themselves. According to the company's statistic, each city has its own interesting point. For instance, Paris has its interesting point of 90, New York has its interesting point of 70, ect. Not any two cities in the world have straight flight so the tour company provide a map to tell its tourists whether they can got a straight flight between any two cities on the map. In order to fly back, the company has made it impossible to make a circle-flight on the half way, using the cities on the map. That is, they marked each city on the map with one number, a city with higher number has no straight flight to a city with lower number.

Note: Weiwei always starts from Hangzhou(in this problem, we assume Hangzhou is always the first city and also the last city, so we mark Hangzhou both 1 andN+1), and its interesting point is always 0.

Now as the leader of the team, Weiwei wants to make a tour as interesting as possible. If you were Weiwei, how did you DIY it?

Input
The input will contain several cases. The first line is an integer T which suggests the number of cases. Then T cases follows.
Each case will begin with an integer N(2 ≤ N ≤ 100) which is the number of cities on the map.
Then N integers follows, representing the interesting point list of the cities.
And then it is an integer M followed by M pairs of integers [Ai, Bi] (1 ≤ i ≤ M). Each pair of [Ai, Bi] indicates that a straight flight is available from City Ai to City Bi.
Output
For each case, your task is to output the maximal summation of interesting points Weiwei and his fellow workers can get through optimal DIYing and the optimal circuit. The format is as the sample. You may assume that there is only one optimal circuit.

Output a blank line between two cases.

Sample Input

2
3
0 70 90
4
1 2
1 3
2 4
3 4
3
0 90 70
4
1 2
1 3
2 4
3 4

Sample Output

CASE 1#
points : 90
circuit : 1->3->1

CASE 2#
points : 90
circuit : 1->2->1

分析与总结:
有点像TSP问题,但是这题已经告诉我们会把最终回来到1的那点看成是n+1点。所以直接当作是求1~n+1的最长路即可。这题还要保存路径。

用单源最短路算法或者用我刚刚学到的Floyd记录路径方法均可。

输出时需要注意,当输出n+1时要把它变成输出1.

代码:

1.  SPFA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;  

const int INF = 0xfffffff;
const int VN  = 105;  

int n,m;
int w[VN][VN];
int point[VN];
int d[VN];
int pre[VN];
bool inq[VN];
int ans[VN];  

void init(){
    point[n] = 0;
    for(int i=0; i<=n; ++i){
        w[i][i] = INF;
        for(int j=i+1; j<=n; ++j)
            w[i][j]=w[j][i]=INF;
    }
}  

void SPFA(int src){
    memset(inq, 0, sizeof(inq));
    memset(pre, -1, sizeof(pre));
    for(int i=1; i<=n; ++i) d[i]=-INF;
    d[src] = 0;
    queue<int>q;
    q.push(src);
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(int v=1; v<=n; ++v)if(w[u][v]!=INF){
            int tmp = d[u] + w[u][v];
            if(d[v] < tmp){
                d[v] = tmp;
                pre[v] = u;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}  

void print_path(int u){
    if(pre[u]==-1){
        printf("1");
        return;
    }
    print_path(pre[u]);
    if(u==n) printf("->%d",1);
    else printf("->%d",u);
}  

int main(){
    int T,u,v,cas=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ++n;
        init();
        for(int i=1; i<n; ++i)
            scanf("%d",&point[i]);
        scanf("%d",&m);
        for(int i=0; i<m; ++i){
            scanf("%d%d",&u,&v);
            w[u][v] = point[v];
        }
        SPFA(1);  

        if(cas!=1)puts("");
        printf("CASE %d#\n", cas++);
        printf("points : %d\n", d[n]);
        printf("circuit : ");
        print_path(n);
        puts("");
    }
    return 0;
}

2. Floyd

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, number
, point
, is
The
hdu 1224、vshduyctwjjdiydllps、free tour、spoj free tour 2、anilos.com free tour,以便于您获取更多的相关知识。

时间: 2024-11-15 07:18:09

HDU 1224 Free DIY Tour的相关文章

最短路专题【完结】

第一题 hdu 1317 XYZZY 点击打开hdu 1317 思路: 1 题目的图是一个有向图,并且可能存在环.第一个点的能量值为100,边的权值利用能量大小,例如2点为-60,如果1->2那么value[1][2] = -602 题目明确指出如果是要win的话,那么必须是经过的每条边都要大于0.那么我们只要把那些经过松弛操作后的点大于0的入队即可,小于等于0的点肯定不会出现在最终的路径上.3 如果存在正环的话,那么就有能量值无限大,那么这个时候只要判断这个点能否到达n4 判断是否是有环还是五

喜欢算法的来帮帮忙 这道题实在是不会了

问题描述 喜欢算法的来帮帮忙 这道题实在是不会了 地址 :http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1005&cid=29617 麻烦贴下代码就行 解决方案 http://zhidao.baidu.com/link?url=zwfY7XXK0ltMcUGzCgW1L-rBh9EdLp60MP9wKcdTYik9vXGCYKqVVZ-8YACrZWOPYoHZoGm6skoRnzsK8QDg3KTPWoKV9F6Qk_fwCbSyF

一个算法问题 最长子串

问题描述 一个算法问题 最长子串 最长子串 Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65535/65535K (Java/Other) Total Submission(s) : 19 Accepted Submission(s) : 1 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description 小E最近开始研究数列,于是小J就给他出了

hdu 1527

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1527 hint:威佐夫博弈 基本类似于模板 #include <iostream> #include <cmath> #include <cstdio> using namespace std; const double q = (1 + sqrt(5.0)) / 2.0; // 黄金分割数 int Wythoff(int a, int b) { if (a > b)

hdu 2551 竹青遍野

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2551 hint:就是读懂题就行了 #include <iostream> #include <cstdio> using namespace std; typedef long long LL; LL data[1005]; int main() { data[0]=0; for(int i=1; i<1005; i++) data[i]+=data[i-1]+i*i*i; LL

hdu 2054 A == B?

http://acm.hdu.edu.cn/showproblem.php?pid=2054 此题巨坑,刚开始我以为是简单的水题,就用strcmp过, but错了,后来经过我苦思冥想,结果还有几组数据 0.0 和 0,1.000和1.0 , 但是我不太确定前面的0是不是有作用我还是写了,但是有人过的时候,前面的0没考虑比如: 002和2可能是相等的,也可能是不想等的所以不用判断,只能说明hdu数据不是很强啊,嘿嘿 代码如下: #include <iostream> #include <c

hdu 4430 Yukari&#039;s Birthday

点击打开链接hdu 4430 思路:枚举r+二分k 分析: 1 题目要求的是找到一组最小的r*k,如果r*k相同那么就找r最小的. 2 很明显k>=2,根据n <= 10^12,那么可以知道r的最大值r<50,所以只要枚举枚举r的值,然后二分k的大小找到所有的解,存入一个结构体里面,然后在对结构体排序,那么这样就可以得到最后的ans 3 注意题目说了中心点最多一个蜡烛,所以写二分的时候应该注意判断的条件: 4 还有可能计算得到结果超了long long直接变成负数所以应该对或则个进行判断

hdu 1238 Substrings

点击打开链接hdu 1238 思路:kmp+暴力枚举子串 分析: 1 题目要求找到一个子串x,满足x或x的逆串是输入的n个字符串的子串,求最大的x,输出x的长度 2 题目的n最大100,每一个字符串的最大长度为100,那么暴力枚举子串就是o(n^2)才10000肯定是不会超时的,但是由于这里涉及到了逆串的问题,所以我们应该还要求出n个子串的逆串,然后在求最大的x. 代码: #include<iostream> #include<algorithm> #include<cstd

hdu 1857 Word Puzzle

点击打开链接hdu 1857 思路:字典树 分析: 1 题目要求的是给定的单词第一个字母在这个矩形里面的最小的坐标 2 矩形的最大500*500,单词的来源有三个方向,并且单词的起点和终点在矩形之内都是可能的.所以的如果利用枚举矩形之内的单词,那么肯定是超内存的 3 所以我们必须考虑另一种的方法就是对单词进行建字典树,那么我们只要去枚举单词的可能的起点,然后进行查找相应的单词是不是在树上,如果是的话就标记一下当前的坐标. 4 注意由于单词的来源有三个方向,但是因为要求的如果下相同的情况下要求坐标