被题意杀
本以为一个种类的物品一定要一起买
看了题解才知道可以先把所有要买的物品买一个，剩下要买的物品就可以得到这个种类的物品能够得到的最大优惠……
所以现在只需要知道：第一次买所有物品一遍时按照什么顺序买最优惠
建一个超级源点向每一个物品连权值等同于其价值的边，对于优惠\((A,B,P)\)从\(A\)向\(B\)连权值为\(P\)的遍，然后一遍最小树形图即可。
注意一个购买数量为\(0\)的点和它的所有出入边都要被忽视
#include//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;}