小店的优惠方案十分简单有趣:
一次消费过程中,如您在本店购买了精制油的话,您购买香皂时就可以享受2.00元/块的优惠价;如果您在本店购买了香皂的话,您购买可乐时就可以享受1.50元/听的优惠价......诸如此类的优惠方案可概括为:如果您在本店购买了商品A的话,您就可以以P元/件的优惠价格购买商品B(购买的数量不限)。
有趣的是,你需要购买同样一些商品,由于不同的买卖顺序,老板可能会叫你付不同数量的钱。比如你需要一块香皂(原价2.50元)、一瓶精制油(原价10.00元)、一听可乐(原价1.80元),如果你按照可乐、精制油、香皂这样的顺序购买的话,老板会问你要13.80元;而如果你按照精制油、香皂、可乐这样的顺序购买的话,您只需付13.50元。
该处居民发现JSOI集训队的队员均擅长电脑程序设计,于是他们请集训队的队员编写一个程序:在告诉你该小店商品的原价,所有优惠方案及所需的商品后,计算至少需要花多少钱(不允许购买任何不必要的商品,即使这样做可能使花的钱更少)。
首先不用买的全部丢掉 , 优惠活动也不用管。
考虑一个最优策略 , 显然我们不会蠢到白白的优惠不要 , 那么一定是先所有要买的物品都买一个 , 然后就能取得所有优惠。直接取最小值当做价格即可。
那么问题就是让所有物品买一次后总价格最小。
这就很像一个生成树了。
由于有些物品可能没有优惠 , 我们建立一个超级点 , 向所有其他物品连原价的边 , 相当于买了超级点其他物品都能以原价的优惠购买。
这样就是要求一个以超级点为根的最小树形图了 , 朱刘算法即可。
简单说明朱刘算法的求解步骤:
首先要明确的一点是每一个点只会有一条入边。
本题code:
#include<bits/stdc++.h>using namespace std;typedef double db;const int M=6000;const int N=51;struct edge{ int u,v;db val; edge(){u=v=0,val=0.0;} edge(int a,int b,db c){u=a,v=b,val=c;}}a[M],b[M];int In[N],vis[N],bel[N],cnt=0,m,n,bcc;db cost[N];int ned[N];db Mi[N];int rt;db ans=0;int flag=0;bool MST(){ for(int i=1;i<=n;++i) In[i]=vis[i]=bel[i]=0;bcc=0,cnt=0; for(int i=1;i<=m;++i) { int u=a[i].u,v=a[i].v;db w=a[i].val; if(!In[v]||a[In[v]].val>w) In[v]=i; } for(int i=flag;i<=n;++i) { if(!flag&&!ned[i]) continue; if(i!=rt) ans+=a[In[i]].val; if(vis[i]) continue; int u=i; for(;u^rt&&vis[u]!=i&&!bel[u];u=a[In[u]].u) vis[u]=i; if(u^rt&&!bel[u]) { ++bcc;while(bel[u]!=bcc) bel[u]=bcc,u=a[In[u]].u; } } if(!bcc) return 0; for(int i=flag;i<=n;++i) { if(!flag&&!ned[i]&&i!=rt) continue; if(!bel[i]) bel[i]=++bcc; } for(int i=1;i<=m;++i) { int u=a[i].u,v=a[i].v;db w=a[i].val; if(bel[u]==bel[v]) continue; db goi=a[In[v]].val;b[++cnt]=(edge){bel[u],bel[v],w-goi}; } for(int i=1;i<=cnt;++i) a[i]=b[i]; n=bcc;m=cnt; return 1;}int main(){ cin>>n;int tot=n;// !! 注意记录啊 for(int i=1;i<=n;++i) cin>>cost[i]>>ned[i],Mi[i]=cost[i]; cin>>m; for(int i=1;i<=m;++i) { int A,B;db P; cin>>A>>B>>P; if(!ned[A]||!ned[B]) --i,--m; else {Mi[B]=min(Mi[B],P);a[i]=edge(A,B,P);} } for(int i=1;i<=n;++i) if(ned[i]) a[++m]=edge(0,i,cost[i]); rt=0;flag=0; while(MST()) rt=bel[rt],flag=1; for(int i=1;i<=tot;++i) { if(ned[i]) { --ned[i]; ans+=Mi[i]*(db)ned[i]; } } printf("%.2lf\n",ans);}