Solution [JSOI2008]小店购物
题目大意:有若干件物品,每个物品有一个原价,购买某件物品后可以以更优价购买另一件物品.每件物品有一个需求数目,既不能多买,也不能少买(如果需求(0)件你就不能买,哪怕可能使得总价最优)
最小树形图
题目分析:看到题解区巨佬的题解,发现此题有一个绝妙的贪心做法.
对于某件物品,我们怎样使得购买它的代价最小呢?我们可以贪心的在这件物品所有的可行方案(原价与优惠价)里面取最小的,做一次乘法运算即可得出答案
关键是,怎样使得这个贪心是正确的呢?我们发现,假如所有物品都被购买了的话,那么就可以保证这个贪心是正确的.那么我们就可以把这个问题分成两个问题:
- 1.求出每个物品都买一件的最小代价和
- 2.所有物品都购买了一件后,我们贪心算出剩余物品的代价和
那么问题(1)怎么解决?
首先,我们对于每一个优惠方案((a,b,p)),都在图中从(a)往(b)连一条权值为(p)的边,这样我们就处理完了优惠方案
对于原价,我们新建一个虚拟节点,并从这个虚拟节点往所有点连一条边,权值为这个物品的原价,这样原图就是一个以虚拟节点为根的有向图
然后,你发现我们这个问题是不是有几个美妙的性质:
- (1.)有向图有根节点
- (2.)所有点都必须被选到(对于那些不需要的点,我们假设它需要,用些处理技巧使它不影响最终答案)
- (3.)使得边权之和最小
然后这不就是最小树形图的板子题了么?
上面所说的处理技巧:
对于一个优惠方案((a,b))我们可以分类讨论:
- 如果物品(a)不需要:那么我们从(a)到(b)连一条权值为(INF)的边.道理很好想,既然物品(a)不能选择,那么选择物品(a)的优惠方案肯定都是非法的,把权值设为(INF)就保证这个方案不会被选到
- 如果物品(b)不需要:那么我们从(a)到(b)连一条权值为(0)的边.既然物品(b)不需要,我们可以看做购买物品(b)不需要任何代价
对于原价的方案,处理起来差不多,详细都在代码注释里了:
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 64;
const int maxm = maxn * maxn;//总边数没有给出,不过是可以算出来的
const double INF = 1e9;
struct Edge{
int from,to;
double dist;
Edge() = default;
Edge(int a,int b,double c):from(a),to(b),dist(c){}
}Edges[maxm];
int head[maxn],nxt[maxm],n,m;
inline void addedge(int from,int to,double dist){
static int tot;
Edges[++tot] = Edge(from,to,dist);
nxt[tot] = head[from];
head[from] = tot;
}
double ine[maxn],ans;
int pre[maxn],vis[maxn],id[maxn],num[maxn],root;//num为每个物品的需求数量
inline void work(){//以下为最小树形图模板(图论的关键不都是建图么)
while(true){
for(int i = 1;i <= n;i++)ine[i] = INF;
for(int i = 1;i <= m;i++){
int u = Edges[i].from,v = Edges[i].to;
if(u != v && Edges[i].dist < ine[v])
ine[v] = Edges[i].dist,pre[v] = u;
}
int cnt = 0;
memset(vis,0,sizeof(vis));
memset(id,0,sizeof(id));
for(int i = 1;i <= n;i++){
if(i == root)continue;
ans += ine[i];
int v = i;
while(vis[v] != i && !id[v] && v != root)
vis[v] = i,v = pre[v];
if(!id[v] && v != root){
id[v] = ++cnt;
for(int u = pre[v];u != v;u = pre[u])
id[u] = cnt;
}
}
if(cnt == 0)break;
for(int i = 1;i <= n;i++)
if(!id[i])id[i] = ++cnt;
for(int i = 1;i <= m;i++){
int u = Edges[i].from,v = Edges[i].to;
Edges[i].from = id[u],Edges[i].to = id[v];
if(id[u] != id[v])Edges[i].dist -= ine[v];
}
root = id[root];
n = cnt;
}
}
double price[maxn];//每个物品的最小代价
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++)//读入每个物品的原价以及需求数量
scanf("%lf %d",&price[i],&num[i]);
for(int i = 1;i <= n;i++)//从虚拟节点连边(原价方案)
addedge(n + 1,i,num[i] == 0 ? 0 : price[i]);//处理不需要的点,使它不影响最终结果
scanf("%d",&m);
for(int i = 1;i <= m;i++){//处理优惠方案
int a,b;double c;
scanf("%d %d %lf",&a,&b,&c);
if(num[a] == 0)addedge(a,b,INF);//分类讨论
else if(num[b] == 0)addedge(a,b,0);
else addedge(a,b,c),price[b] = min(price[b],c);//更新购买每件物品的最优价格,便于下面贪心
}
for(int i = 1;i <= n;i++)//贪心购买物品
ans += (num[i] - 1) * price[i];
root = n + 1;//根
m = m + n;//连接了虚拟边,边数要相应增加
n = n + 1;//同上
work();//最小树形图,求出每个物品都买一件的最小代价
printf("%.2lf
",ans);
return 0;
}