首页 > ACM题库 > HDU-杭电 > HDU 3696-Farm Game-最短路径-[解题报告]HOJ
2014
11-30

HDU 3696-Farm Game-最短路径-[解题报告]HOJ

Farm Game

问题描述 :

“Farm Game” is one of the most popular games in online community. In the community each player has a virtual farm. The farmer can decide to plant some kinds of crops like wheat or paddy, and buy the corresponding crop seeds. After they grow up, The farmer can harvest the crops and sell them to gain virtual money. The farmer can plant advanced crops like soybean, watermelon or pumpkin, as well as fruits like lychee or mango.

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.

输入:

The input contains several test cases. The first line of each test case contains an integers N (N<=10000) representing that there are N kinds of products in Jack’s farm. The product categories are numbered for 1 to N. In the following N lines, the ith line contains two real numbers p and w, meaning that the price for the ith kind of product is p per pound and Jack has w pounds of the ith kind of product.

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 a0, b1, a1, b2, a2, …, bk-1, ak-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 ai-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.

输出:

The input contains several test cases. The first line of each test case contains an integers N (N<=10000) representing that there are N kinds of products in Jack’s farm. The product categories are numbered for 1 to N. In the following N lines, the ith line contains two real numbers p and w, meaning that the price for the ith kind of product is p per pound and Jack has w pounds of the ith kind of product.

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 a0, b1, a1, b2, a2, …, bk-1, ak-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 ai-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种产品,每种产品有一定的价值和数量,
某些产品可以转换为另一种产品,有一定的转换率(转换中数量有损失)。
求最多能获得多少价值。
在转换过程中,转换率是要乘起来的,最后再乘上转换成的产品的价值,
如果这个价值比原来的大,就转换产品。
由于可以通过多种路径转换成另一种产品,所以用SPFA求最长路。
乘法通过log取对数转换为加法。
现在需要知道每个产品所能转换得到的最多价值,也就是求每个点到其他点最长路的最大值。
加一个附加点s,所有点连接到s,边权为log(p[i]),这样直接求每个点到s的最长路就可以知道最大值了。
这样需要n次SPFA,不过如果我们把图反向,求一次s开始的最长路,就可以知道所有点能转换的最大价值了。
最后再把这些值和以前的价值比较,得到每种产品的最大价值。
PS:由于是一个有向无环图,所以网上一些代码是DP或者拓扑排序。
代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 10005
using namespace std;

int n,m,num,adj[N],q[N];
bool f[N];
double low[N],p[N],w[N];
struct edge
{
int v,pre;
double w;
edge(){}
edge(int vv,double ww,int p){v=vv;w=ww;pre=p;}
}e[N*5];
void insert(int u,int v,double w)
{
e[num]=edge(v,w,adj[u]);
adj[u]=num++;
}
void spfa(int x)
{
int i,v,head=0,tail=0;
memset(f,0,sizeof(f));
memset(low,-0x3f,sizeof(low));
low[x]=0;
q[++tail]=x;
while(head!=tail)
{
x=q[head=(head+1)%N];
f[x]=0;
for(i=adj[x];~i;i=e[i].pre)
if(low[v=e[i].v]<low[x]+e[i].w)
{
low[v]=low[x]+e[i].w;
if(!f[v])
{
f[v]=1;
q[tail=(tail+1)%N]=v;
}
}
}
}
int main()
{
while(scanf(“%d”,&n),n)
{
int i,k,a,b;
double t,ans=0;
num=0;
memset(adj,-1,sizeof(adj));
for(i=1;i<=n;i++)
scanf(“%lf%lf”,p+i,w+i);
scanf(“%d”,&m);
while(m–)
{
scanf(“%d”,&k);
scanf(“%d”,&a);
for(i=1;i<k;i++)
{
scanf(“%lf%d”,&t,&b);
insert(b,a,log(t));
a=b;
}
}
for(i=1;i<=n;i++)
insert(0,i,log(p[i]));
spfa(0);
for(i=1;i<=n;i++)
{
if(p[i]<exp(low[i]))
p[i]=exp(low[i]);
ans+=p[i]*w[i];
}
printf(“%.2f\n”,ans);
}
}

参考:http://blog.csdn.net/power721/article/details/6968014


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

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