首页 > ACM题库 > HDU-杭电 > hdu 3769 Stack Machine待解决[解题报告]C++
2015
04-10

hdu 3769 Stack Machine待解决[解题报告]C++

Stack Machine

问题描述 :

A mathematician observes one person get on a bus. Then two people get off the bus. The mathematician says: "If one more person gets on the bus, the bus will be empty."

A stack machine is a special kind of bus. It only has doors at the front, and it is so narrow that the people on the bus cannot move past each other. Of the people on the bus, the person who got on the bus last must be the first to get off.

The bus travels in a city in which roads connect intersections, and all the roads are unidirectional. Along each road, a person either gets on or off the bus.

The mathematician does not know the identity of the bus passengers, but can estimate their height. Note that there may be multiple people with the same height.

Your task is to plan the route of the bus. The bus must be empty at the beginning and end of the route. Along the route, it must pick up and drop off the people corresponding to the roads it travels on. The height of the person that gets on or off the bus is fixed for each road.

输入:

The first line of input contains a single integer, the number of test cases to follow. Each test case begins with a line containing three integers N, M, Q, the number of intersections and roads in the city and the number of queries, respectively. The number of intersections is between 1 and 100, inclusive. The number of roads and the number of queries are each between 1 and 100000, inclusive. Intersections in the city are numbered from 1 to N. The first line of each test case is followed by M lines describing the roads. Each of these lines contains three integers X, Y, and Z. These integers indicate that a road exists from intersection X to intersection Y, and that when the bus travels on this road, a person who is Z centimetres tall gets on the bus, if Z is positive, or a person who is -Z centimetres tall gets off the bus, if Z is negative. For example, Z=170 indicates that a 170 cm tall person gets on the bus, and Z=-170 indicates that a 170 cm tall person gets off the bus. Each person is at least 40 cm and at most 220 cm tall. The lines describing the roads are followed by Q more lines, each describing a query. A line describing a query contains two integers, the beginning and ending intersections of the bus route.

输出:

The first line of input contains a single integer, the number of test cases to follow. Each test case begins with a line containing three integers N, M, Q, the number of intersections and roads in the city and the number of queries, respectively. The number of intersections is between 1 and 100, inclusive. The number of roads and the number of queries are each between 1 and 100000, inclusive. Intersections in the city are numbered from 1 to N. The first line of each test case is followed by M lines describing the roads. Each of these lines contains three integers X, Y, and Z. These integers indicate that a road exists from intersection X to intersection Y, and that when the bus travels on this road, a person who is Z centimetres tall gets on the bus, if Z is positive, or a person who is -Z centimetres tall gets off the bus, if Z is negative. For example, Z=170 indicates that a 170 cm tall person gets on the bus, and Z=-170 indicates that a 170 cm tall person gets off the bus. Each person is at least 40 cm and at most 220 cm tall. The lines describing the roads are followed by Q more lines, each describing a query. A line describing a query contains two integers, the beginning and ending intersections of the bus route.

样例输入:

1
2 2 4
1 2 100
2 1 -100
1 1
2 2
1 2
2 1

样例输出:

2
impossible
impossible
impossible


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3