【题解】旅行-C++

Description

某趟列车的最大载客容量为V人，沿途共有n个停靠站，其中始发站为第1站，终点站为第n站。在第1站至第n-1站之

间，共有m个团队申请购票搭乘，若规定：（1）对于某个团队的购票申请，要么全部满足，要么全部拒绝，即不允

许只满足部分。（2）每个乘客的搭乘费用为其所乘站数。问：应如何选择这些购票申请，能使该趟列车获得最大

的搭乘费用？其中，每个团队的购票申请格式是以空格分隔的三个整数：a b t，即表示有t个人需要从第a站点

乘至第b站点（注：每个团队的所有人员都必须同时在a站上车，且必须同时在后面的b站下车）。

Input

有若干行。其中：

第1行只有三个整数n，m，v，分别表示站点数、申请数、列车的最大载客容量。

这三个整数之间都以一个空格分隔。

第2行至第m+1行，每行有三个整数，中间都以一个空格分隔。

其中第k+1行的三个整数a，b，t表示第k个申请，含义为：有t个人需要从第a站乘至第b站。

1≤n≤10；1≤m≤18，1<=V<=200

Output

只有一行，该行只有一个整数，为该列车能获得的最大搭乘费用。

Sample Input

3 3 5

1 2 2

2 3 5

1 3 4

Sample Output

8

//当只选择第3个申请时，能获得的最大搭乘费用为（3-1）*4=8

这道题目乍一看像个背包问题，但其实和背包基本不一样。。。接下来看一下这道题的正确解法（假装正确）

存数据我就用了a,b,t三个数组，本来想开结构体但是后面玩炸了就换成了这个

然后就是dfs的过程，dfs的边界在m站搜索完毕之后，所以如果达到边界，我们就要判断这种状态是否满足条件，满足条件再考虑是否更新ans，对于是否满足条件，可以写一个check函数，用w[i]表示第i站增加的人数（可以是负数），然后遍历一遍，如果过程中总人数超过n则不满足情况。

如果没有达到边界，就考虑是否同意团队请求，拓展是或否两种情况即可。

下面是代码：

#include<bits/stdc++.h>

using namespace std;

int n,m,v,ans=0,w[66];

bool team[1010];

int a[66],b[66],t[66];

bool check()

{

	int p=0;

	for(int i=1;i<=n;i++)

	{

		p+=w[i];

		if(p>v)return false;

	}

	return true;

}

void dfs(int dep)

{

	if(dep==m+1)

	{

		int an=0;

		memset(w,0,sizeof(w));

		for(int i=1;i<=m;i++)

		{

			if(team[i])

			{

				w[a[i]]+=t[i];

				w[b[i]]-=t[i];

				an+=t[i]*(b[i]-a[i]);

			}

		}

		if(check())

		{

			ans=max(ans,an);

		}

		return;

	}

	dfs(dep+1);

	team[dep]=1;

	dfs(dep+1);

	team[dep]=0;

	return;

}

int main()

{

	cin>>n>>m>>v;

	for(int i=1;i<=m;i++)

	{

		cin>>a[i]>>b[i]>>t[i];

	}

	dfs(1);

	cout<<ans<<endl;

	return 0;

}

ov.

巴特西

【题解】旅行-C++

最新文章

热门文章