传送门
被题意杀
本以为一个种类的物品一定要一起买
看了题解才知道可以先把所有要买的物品买一个，剩下要买的物品就可以得到这个种类的物品能够得到的最大优惠……
所以现在只需要知道：第一次买所有物品一遍时按照什么顺序买最优惠
建一个超级源点向每一个物品连权值等同于其价值的边，对于优惠\((A,B,P)\)从\(A\)向\(B\)连权值为\(P\)的遍，然后一遍最小树形图即可。
注意一个购买数量为\(0\)的点和它的所有出入边都要被忽视
#include<bits/stdc++.h>//This code is written by Itstusing namespace std;struct Edge{ ???int s , t; ???double w;}Ed[5010];int id[101] , vis[101] , num[101] , pre[101];int N , M , cntEd;double sum , pri[101] , dis[101];bool have[101][101];void work(int rt){ ???while(1){ ???????memset(vis , 0x3f , sizeof(vis)); ???????memset(id , -1 , sizeof(id)); ???????fill(dis , dis + N + 1 , 5e7); ???????int cnt = 0; ???????for(int i = 1 ; i <= cntEd ; ++i) ???????????if(Ed[i].s != Ed[i].t && dis[Ed[i].t] > Ed[i].w){ ???????????????dis[Ed[i].t] = Ed[i].w; ???????????????pre[Ed[i].t] = Ed[i].s; ???????????} ???????for(int i = 0 ; i <= N ; ++i){ ???????????if(i == rt) ???????????????continue; ???????????sum += dis[i]; ???????????int u = i; ???????????vis[i] = i; ???????????while(u != rt && vis[pre[u]] > i) ???????????????vis[u = pre[u]] = i; ???????????if(u != rt && vis[pre[u]] == i){ ???????????????do{ ???????????????????id[u] = cnt; ???????????????????u = pre[u]; ???????????????}while(id[u] == -1); ???????????????++cnt; ???????????} ???????} ???????if(!cnt) ???????????break; ???????for(int i = 0 ; i <= N ; ++i) ???????????if(id[i] == -1) ???????????????id[i] = cnt++; ???????for(int i = 1 ; i <= cntEd ; ++i){ ???????????Ed[i].w -= dis[Ed[i].t]; ???????????Ed[i].s = id[Ed[i].s]; ???????????Ed[i].t = id[Ed[i].t]; ???????} ???????N = cnt - 1; ???????rt = id[rt]; ???}}signed main(){ ???#ifndef ONLINE_JUDGE ???//freopen("in" , "r" , stdin); ???//freopen("out" , "w" , stdout); ???#endif ???cin >> N; ???for(int i = 1 ; i <= N ; ++i){ ???????cin >> pri[i] >> num[i]; ???????Ed[++cntEd].s = 0; ???????Ed[cntEd].t = i; ???????if(num[i]) ???????????Ed[cntEd].w = pri[i]; ???} ???cin >> M; ???for(int i = 1 ; i <= M ; ++i){ ???????int a , b; ???????double c; ???????cin >> a >> b >> c; ???????if(num[a] && num[b]){ ???????????Ed[++cntEd].s = a; ???????????Ed[cntEd].t = b; ???????????Ed[cntEd].w = c; ???????????pri[b] = min(pri[b] , c); ???????} ???} ???for(int i = 1 ; i <= N ; ++i) ???????if(num[i]) ???????????sum += (num[i] - 1) * pri[i]; ???work(0); ???cout << fixed << setprecision(2) << sum; ???return 0;}Luogu2792 JSOI2008 小店购物 最小树形图
原文地址：https://www.cnblogs.com/Itst/p/10351648.html