本文主要是介绍HDOJ 3696 Farm Game 【spfa】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Farm Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 62768/32768 K (Java/Others)Total Submission(s): 670 Accepted Submission(s): 258
Feeding animals is also allowed. The farmer can buy chicken, rabbits or cows and feeds them by specific crops or fruits. For example, chicken eat wheat. When the animals grow up, they can also “output” some products. The farmer can collect eggs and milk from hens and cows. They may be sold in a better price than the original crops.
When the farmer gets richer, manufacturing industry can be set up by starting up some machines. For example, Cheese Machine can transfer milk to cheese to get better profits and Textile Machine can spin cony hair to make sweaters. At this time, a production chain appeared in the farm.
Selling the products can get profits. Different products may have different price. After gained some products, the farmer can decide whether to sell them or use them as animal food or machine material to get advanced products with higher price.
Jack is taking part in this online community game and he wants to get as higher profits as possible. His farm has the extremely high level so that he could feed various animals and build several manufacturing lines to convert some products to other products.
In short, some kinds of products can be transformed into other kinds of products. For example, 1 pound of milk can be transformed into 0.5 pound of cheese, and 1 pound of crops can be transformed into 0.1 pound of eggs, etc. Every kind of product has a price. Now Jack tell you the amount of every kind of product he has, and the transform relationship among all kinds of products, please help Jack to figure out how much money he can make at most when he sell out all his products.
Please note that there is a transforming rule: if product A can be transformed into product B directly or indirectly, then product B can never be transformed into product A, no matter directly or indirectly.
Then there is a line containing an integer M (M<=25000) meaning that the following M lines describes the transform relationship among all kinds of products. Each one of those M lines is in the format below:
K a 0, b 1, a 1, b 2, a 2, …, b k-1, a k-1
K is an integer, and 2×K-1 numbers follows K. ai is an integer representing product category number. bi is a real number meaning that 1 pound of product a i-1 can be transformed into bi pound of product ai.
The total sum of K in all M lines is less than 50000.
The input file is ended by a single line containing an integer 0.
2 2.5 10 5 0 1 2 1 0.5 2 2 2.5 10 5 0 1 2 1 0.8 2 0
25.00 40.00
题意:有n种物品要卖,每种物品有自己的单价和现在有的重量,根据题意,可以将一种物品转换为另外一种物品,但是有转换百分比(例如1 0.8 2,意思将1单位的物品1转化为物品2之后为0.8单位的物品2)。求最后可以得到的总的钱数。
分析:根据题意这道题可以转换成一个有向无环图,因为可以间接转化就是1——》2,之后2——》3,这样子转化,我们需要找到一个最长的转换路径(有最大利润的),我们可以设置一个点(这个点就代表原来自身的价钱),用spfa求出每一个点到该点的最长路径深度,需要n-1次,我们反过来用这个点求取到每一个点的深度,这样只需要一次就好了。因为有叠成,我们用log就可以转化为加法。
代码:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
const int M = 1e4+5;
using namespace std;struct node{int to, next;double v;
}e[M*4];
int head[M*4];
double p[M], w[M], low[M];
int n, tot;
bool vis[M];
//int que[M];void add(int a, int b, double c){e[tot].to = b;e[tot].next = head[a];e[tot].v = c;head[a] = tot++;
}void spfa(int u){queue<int >q;memset(vis, 0, sizeof(vis));memset(low, -0x3f, sizeof(low));q.push(u);//vis[u] = 1;low[u] = 0;while(!q.empty()){int temp = q.front();q.pop();for(int i = head[temp]; ~i; i = e[i].next){int v = e[i].to;if(low[v] < low[temp]+e[i].v){low[v] = low[temp]+e[i].v;if(!vis[v]){vis[v] = 1;q.push(v);}}}}
}int main(){while(scanf("%d", &n), n){int i;for(i = 1; i <= n; ++ i) scanf("%lf%lf", p+i, w+i);int a, b, m, k;double temp;tot = 0;scanf("%d", &m);memset(head, -1, sizeof(head));while(m --){scanf("%d%d", &k, &a);for(i = 1; i < k; ++ i){scanf("%lf%d", &temp, &b);add(b, a, log(temp)); //因为是反过来求的所以方向也需要反过来a = b;}}for(i = 1; i <= n; ++ i){add(0, i, log(p[i]));}spfa(0);double ans = 0;for(i = 1; i <= n; ++ i){if(p[i] < exp(low[i]))p[i] = exp(low[i]);ans += p[i]*w[i];}printf("%.2lf\n", ans);}return 0;
}
这篇关于HDOJ 3696 Farm Game 【spfa】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!