区块链技术博客
www.b2bchain.cn

Volunteer recruitment

这篇文章主要介绍了Volunteer recruitment,通过具体代码讲解7739并且分析了Volunteer recruitment的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了Volunteer recruitment。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=7739。具体如下:

Description

Suppose you will recruit a group of volunteers for a coming event. It is estimated that this event will take N days to complete, and the i(th) day needs at least Ai volunteers. The number of kinds of volunteers is M. The volunteers of i(th) kind can volunteer from the Si day to the Fi day and the recruit fee is Ci. In order to do his job well, you hope to recruit enough volunteers with least money. Please give an optimal plan.

note: i(th) means the ordinal of this number is i

Input

The first line presents two integers: N, M. The second line contains N nonnegative integers presenting the numbers of volunteers each day needs. Each of the other lines contain three integers: Si, Fi, Ci

note: You can recruit each kind of volunteers as many as possible.

Output

Just a number meaning the total money of your optimal plan.

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

14

Hint

1<=N<=200, 1<=M<=1000, 题目中所有数据不超过2^31-1

 

 #include <iostream> #include <cmath> #define N 1010 #define M 10100 using namespace std; const double INF = 1e10; const double eps = 1e-7; int n, m; double A[M][N], b[M], c[N], v; void Pivot(int l, int e) { 	b[l] /= A[l][e]; 	for (int i = 1; i <= n; i++) 		if (i != e) 			A[l][i] /= A[l][e]; 	A[l][e] = 1 / A[l][e]; 	for (int i = 1; i <= m; i++) 		if (i != l && fabs(A[i][e])>eps) 		{ 			b[i] -= A[i][e] * b[l]; 			for (int j = 1; j <= n; j++) 				if (j != e) 					A[i][j] -= A[i][e] * A[l][j]; 			A[i][e] = -A[i][e] * A[l][e]; 		}  	v += c[e] * b[l]; 	for (int i = 1; i <= n; i++) 		if (i != e) 			c[i] -= c[e] * A[l][i]; 	c[e] = -c[e] * A[l][e]; } double Simplex() { 	int i, l, e; 	while (true) 	{ 		for (i = 1; i <= n; i++) 			if (c[i]>eps) break; 		if ((e = i) == n + 1) return v; 		double tmp = INF; 		for (i = 1; i <= m; i++) 			if (A[i][e]>eps && b[i] / A[i][e]<tmp) 				tmp = b[i] / A[i][e], l = i; 		if (tmp == INF) return INF; 		Pivot(l, e); 	} } int main() { 	cin >> n >> m; 	for (int i = 1; i <= n; i++) cin>>c[i]; 	for (int i = 1, x, y; i <= m; i++) 	{ 		cin>>x>>y>>b[i]; 		for (int j = x; j <= y; j++) 			A[i][j] = 1; 	} 	double ans = Simplex(); 	cout<< int(ans + 0.5); 	return 0; } 

 

本文地址https://www.b2bchain.cn/?p=7739

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Volunteer recruitment
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们