首页 > ACM题库 > HDU-杭电 > HDU 1653 Laser Lines-Dijkstra-[解题报告] C++
2013
12-21

HDU 1653 Laser Lines-Dijkstra-[解题报告] C++

Laser Lines

问题描述 :

A computer chip manufacturer has discovered a new way to combine opto-electronics and ordinary electronics by forming light-emitting and receiving nodes on the surface of the chip. These can be used to send messages to each other in a direct line-of-sight manner, thereby speeding up operation considerably by allowing a much greater density of information transfer. One difficulty is that the nodes must all be able to send messages to each other; no node should block the line-of-sight between two other nodes. The manufacturing method ensures that the nodes will be positioned exactly on the points of a lattice covering the chip, so their coordinates are given by integers between 0 and 9999 (inclusive) except that for technical reasons no node can appear at point (0, 0).

Write a program that will read in sets of coordinates of these nodes and determine whether any of them lie on lines containing three or more nodes. Because of the layout method used, it is envisaged that there may well be several lines containing three nodes, but that `longer’ lines will be increasingly rare. However, no line will contain more than 10 points.

输入:

Input will consist of a series of data sets, each set containing the coordinates of between 3 and 300 points (both inclusive). Each set will start on a new line.

The coordinates will be pairs of integers in the range 0 to 9999 and each set will be terminated by a pair of zeroes (0 0). Successive numbers will be separated by one or more spaces; in addition a data set may be split into several lines, such splits will only occur between coordinate pairs and never between the elements of a coordinate pair. The entire file will also be terminated by a pair of zeroes (0 0).

Note that there will be several test cases, but only one will contain more than 100 points.

输出:

Output, for each set, is either the message "No lines were found", or the message "The following lines were found:", followed by the sets of points lying on straight lines, each set ordered first by x, and if the x’s are equal, then by y.

All coordinates are in a field of width 4, and are separated by a comma; the points are delimited by brackets, with no spaces between successive points. The lines themselves are ordered in a similar manner to the points on each line; i.e. by considering the first point on each line, and if more than one line starts at that point, by considering the second point on the line.

样例输入:

  5 5 8 7 14 11 4 8   20 15
12 6  18 21 0  0
5 5 8 8 14 13 0 0
5 5 25 17 20 23 10 11 20 14 15 11 0 0
0 0

样例输出:

The following lines were found: 
(   4,   8)(   8,   7)(  12,   6)
(   5,   5)(   8,   7)(  14,  11)(  20,  15)
(  12,   6)(  14,  11)(  18,  21)
No lines were found
The following lines were found: 
(   5,   5)(  10,  11)(  20,  23)
(   5,   5)(  15,  11)(  20,  14)(  25,  17)

题意:给出了城市数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. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.