题目大意

农场有n种产品，他们之间可以通过牲畜或机械进行加工转化。转化形式为：1单位的产品A可以转化为x单位的产品B，其中x是大于0的实数。另外，每一种产品有不同的售价，第i种产品的单价为Pi。现给出若干初始产品，请将其经过适当加工转化，然后全部卖出，使得最终获利最大。

思路

核心思想是利用深搜作预处理求出每种产品1单位可以换取的最大钱数。

代码

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#define MAXSIZE 10000
int n,m;
double price[MAXSIZE+1],origin[MAXSIZE+1],mark[MAXSIZE+1];
//price[]存储每种产品的单位售价。 
//origin[]存储每种产品的数量。 
//mark[]存储每种产品1单位能换取的最大钱数。 
vector< pair<int,double> > map[MAXSIZE+1];
//pair<产品编号，换取的数量>
//map[]用于存储产品间的转换关系。 
void init()
//初始化 
{
	for(int i=1;i<=n;i++)
	{
		price[i]=0;
		origin[i]=0;
		mark[i]=0;
		map[i].clear();
	}
}
void input()
//输入 
{
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&price[i],&origin[i]);
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		int k,pre,now;
		double b;
		scanf("%d%d",&k,&pre);
		for(int j=0;j<2*k-2;j++)
			if(j%2)
			{
				scanf("%d",&now);
				map[pre].push_back(pair<int,double>(now,b));
				pre=now;
			}
			else
				scanf("%lf",&b);
	}
}
double dfs(int x)
//dfs(x)的返回值为编号为x的产品1单位所能换取的最大钱数。
//深搜进行的同时，对mark[]进行了赋值。 
{
	if(mark[x])
		return mark[x];
	int size=map[x].size();
	if(size==0)
		return mark[x]=price[x];
	double max=price[x];
	for(int i=0;i<size;i++)
	{
		double temp=map[x][i].second*dfs(map[x][i].first);
		max=max>temp?max:temp;
	}
	return mark[x]=max;
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		init();
		input();
		for(int i=1;i<=n;i++)
			dfs(i);
		double sum=0;
		for(int i=1;i<=n;i++)
			sum+=origin[i]*mark[i];
		printf("%.2lf\n",sum);
	}
}