首页 > ACM题库 > HDU-杭电 > Hdu 1456 Transportation-回溯[解题报告] C++
2013
12-11

Hdu 1456 Transportation-回溯[解题报告] C++

Transportation

问题描述 :

Ruratania is just entering capitalism and is establishing new enterprising activities in many fields in- cluding transport. The transportation company TransRuratania is starting a new express train from city A to city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station number m. The company runs an experiment in order to improve passenger transportation capacity and thus to increase its earnings. The train has a maximum capacity n passengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.Write a program which for the given list of orders from single stations on the way from A to B determines the biggest possible total earning of the TransRuratania company. The earning from one accepted order is the product of the number of passengers included in the order and the price of their train tickets. The total earning is the sum of the earnings from all accepted orders.

输入:

The input file is divided into blocks. The first line in each block contains three integers: passenger capacity n of the train, the number of the city B station and the number of ticket orders from all stations. The next lines contain the ticket orders. Each ticket order consists of three integers: starting station, destination station, number of passengers. In one block there can be maximum 22 orders. The number of the city B station will be at most 7. The block where all three numbers in the first line are equal to zero denotes the end of the input file.

输出:

The output file consists of lines corresponding to the blocks of the input file except the terminating block. Each such line contains the biggest possible total earning.

样例输入:

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

样例输出:

19
34


这题题意都理解了好久,先输入3个数,代表车可以承载的乘客上限、站点数、有几份订单,接着几行输入订单信息,每份订单包含3个信息,起点站,终点站,乘客数,订单可以接可以不接,但是接了就要接纳所有乘客,每份订单赚钱为经过几个站点乘乘客数。要求出最大收益。

订单接收后,在起点站乘客上车,在终点站乘客下车,。。一开始的考虑是每份订单进行深搜,每份订单都有2种情况:接与不接。这样的话直接TLE了,订单数最大有22, 一共要2的22次方次。。。

后来卡了好久,没办法参考了个题解。。觉得挺巧妙的地方:
用一个数组来存放:如果接受了这份订单,那么每站的乘客数会变成多少,如果超过数量直接跳过。如果没一个超过的。代表此份订单可接,之后回溯的时候,就回溯存乘客数的那个数组即可。。

代码

#include <stdio.h>
#include <string.h>

int n, m, t;
struct Q
{
    int star;
    int end;
    int p;
} ti[25];
int max;
int nb[8];
int judge(int num)
{
    for (int i = ti[num].star; i < ti[num].end; i ++)
    {
	nb[i] += ti[num].p;
	if (nb[i] > n)
	    return 0;
    }
    return 1;
}
void dfs(int num, int sum)
{
    if (num == t)
    {
	if (max < sum)
	{
	    max = sum;
	}	  
	return;	
    }
    int save[8];
    dfs(num + 1, sum);
    for (int i = 0; i < m; i++)
    {
	save[i] = nb[i];
    }
    if (judge(num))
    {	
	dfs(num + 1, sum + (ti[num].end - ti[num].star) * ti[num].p);
    }
    for (int i = 0; i < m ; i ++)
    {
	nb[i] = save[i];
    }
}
int main()
{
    while (scanf("%d%d%d", &n, &m, &t) != EOF && n || m || t)
    {
	max = 0;
	memset(nb, 0, sizeof(nb));
	memset(ti, 0, sizeof(ti));
	for (int i = 0; i < t; i ++)
	{
	    scanf("%d%d%d", &ti[i].star, &ti[i].end, &ti[i].p);

	}
	dfs(0, 0);
	printf("%d\n", max);
    }
    return 0;
}

转自:http://blog.csdn.net/accelerator_/article/details/9394459


,
  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

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

  4. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法