https://www.luogu.org/problem/show?pid=2792
题目背景
JSOI集训队的队员发现，在他们经常活动的集训地，有一个小店因为其丰富的经营优惠方案深受附近居民的青睐，生意红火。
题目描述
小店的优惠方案十分简单有趣：
一次消费过程中，如您在本店购买了精制油的话，您购买香皂时就可以享受2.00元/块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受1.50元/听的优惠价......诸如此类的优惠方案可概括为：如果您在本店购买了商品A的话，您就可以以P元/件的优惠价格购买商品B（购买的数量不限）。
有趣的是，你需要购买同样一些商品，由于不同的买卖顺序，老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价2.50元）、一瓶精制油（原价10.00元）、一听可乐（原价1.80元），如果你按照可乐、精制油、香皂这样的顺序购买的话，老板会问你要13.80元；而如果你按照精制油、香皂、可乐这样的顺序购买的话，您只需付13.50元。
该处居民发现JSOI集训队的队员均擅长电脑程序设计，于是他们请集训队的队员编写一个程序：在告诉你该小店商品的原价，所有优惠方案及所需的商品后，计算至少需要花多少钱（不允许购买任何不必要的商品，即使这样做可能使花的钱更少）。
输入输出格式
输入格式：
输入文件第一行为一个整数n（1<=n<=50），表示小店的商品总数。
接下来是n行，其中第（i+1）行由一个实数ci（0<ci<=1000）和一个整数mi（0<=mi<=100）组成，其间由一个空格分隔，分别表示第i种商品的原价和所需数量。第（n+2）行又是一个整数k，表示小店的优惠方案总数。
接着k行，每行有二个整数A，B（1<=A,B<=n）和一个实数P（0<=P<1000），表示一种优惠方案，即如果您购买了商品A，您就可以以P元/件的优惠价格购买商品B，P小于商品B的原价。所有优惠方案的（A，B）都是不同的。为了方便老板不收分币，所以所有价格都不出现单位分。
输出格式：
输出只有一个实数，表示最少需要花多少钱。输出实数须保留两位小数。
输入输出样例
410.00 11.80 13.00 02.50 221 4 2.004 2 1.50
15.50
不需要买的商品去掉
跑一遍最小树形图作为第一次买每个商品的花费
然后所有的商品就可以以最低价买下来
#include<cstdio>#include<cstring>#include<algorithm>#define N 52#define M 100001#define inf 2e9using namespace std;int pre[N],vis[N],col[N];int n,m,V,E;int dy[N],sum[N];double in[N],minn[N];struct node{ ???int u,v; ???double w;}e[M+N];double directed_MST(){ ???double ans=0; ???int cirnum,to,root=0; ???while(1) ???{ ???????for(int i=0;i<V;i++) in[i]=inf; ???????for(int i=1;i<=E;i++) ???????{ ???????????if(in[e[i].v]>e[i].w && e[i].u!=e[i].v) ???????????{ ???????????????in[e[i].v]=e[i].w; ???????????????pre[e[i].v]=e[i].u; ???????????} ???????} ???????cirnum=0; ???????memset(vis,-1,sizeof(vis)); ???????memset(col,-1,sizeof(col)); ???????in[root]=0; ???????for(int i=0;i<V;i++) ???????{ ???????????ans+=in[i]; ???????????to=i; ???????????while(vis[to]!=i && col[to]==-1 && to!=root) ???????????{ ???????????????vis[to]=i; ???????????????to=pre[to]; ???????????} ???????????if(col[to]==-1 && to!=root) ???????????{ ???????????????for(int nt=pre[to];to!=nt;nt=pre[nt]) ???????????????????col[nt]=cirnum; ???????????????col[to]=cirnum++; ???????????} ???????} ???????if(!cirnum) return ans; ???????for(int i=0;i<V;i++) ????????????if(col[i]==-1) col[i]=cirnum++; ???????for(int i=1;i<=E;i++) ???????{ ???????????to=e[i].v; ???????????e[i].u=col[e[i].u]; ???????????e[i].v=col[e[i].v]; ???????????if(e[i].u!=e[i].v) e[i].w-=in[to]; ???????} ????????V=cirnum; ???????root=col[root]; ???} ???????return ans;}int main(){ ???scanf("%d",&n); ???double p; int w; ????for(int i=1;i<=n;i++) ???{ ???????scanf("%lf%d",&p,&w); ???????if(w) ???????{ ???????????dy[i]=++V; ???????????????E++; ???????????e[E].u=0; e[E].v=i; e[E].w=p; ???????????sum[V]=w-1; ???????????minn[V]=p; ???????} ???} ???scanf("%d",&m); ???int u,v; ???while(m--) ???{ ???????scanf("%d%d%lf",&u,&v,&p); ???????if(!dy[u] || !dy[v]) continue; ???????E++; ???????e[E].u=dy[u]; e[E].v=dy[v]; e[E].w=p; ???????minn[dy[v]]=min(minn[dy[v]],p); ???} ???V++; ???double ans=0; ???for(int i=1;i<V;i++) ans+=sum[i]*minn[i]; ???ans+=directed_MST(); ???printf("%.2lf",ans);}JSOI2008 小店购物
原文地址：http://www.cnblogs.com/TheRoadToTheGold/p/7435667.html