由于最后要买的东西是一定的，只是顺序不同，所以可以逆向思维，求最多能省多少钱。

对于一个优惠方案，如果A在B前面买，那么对于每一个B都能有优惠，所以连一条边，由A向B，边权为在这种情况下买B总共能省多少钱，即$(c[B]-P)*m[B]$

对于这个图，选出若干条边，使这些边不能形成环，这样就能找到至少一个拓扑序，使得选出的这些边代表的优惠条件能同时满足，此时省下的钱即为边权和。

与Kruskal最大生成树类似，将所有边从大到小排序，若加入该边后没有形成环，就把这条边加入到新图中。

不知道是思路有问题，还是打挂了可能都有

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1010;
double c[maxN],m[maxN];
bool flag[maxN][maxN];
struct node
{
    int u,v;
    double w;
    bool operator < (const node &x)const{return w>x.w;}
}edge[maxN];
int main()
{
    int N,K;
    double ans=0.0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%lf%lf",&c[i],&m[i]);
        ans+=c[i]*m[i];
    }
    scanf("%d",&K);
    for(int i=1;i<=K;i++)
    {
        int u,v;
        double p;
        scanf("%d%d%lf",&u,&v,&p);
        edge[i]={u,v,(c[v]-p)*m[v]};
    }
    sort(edge+1,edge+1+K);
    for(int i=1;i<=N;i++)flag[i][i]=1;
    for(int i=1;i<=K;i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
        double w=edge[i].w;
        if(flag[v][u])continue;
        for(int x=1;x<=N;x++)
            if(flag[x][u]==1)flag[x][v]=1;
        ans-=w;
    }
    printf("%.2lf",ans);
}

提交记录

样例过了，全WA，输出都是负值。