题目：

一看就是0/1分数规划。但不能直接套模板，因为有个商品种类的限制。

　　考虑从a买在b卖，商品种类根本没用，关注的是最大营利。于是可以考虑暴枚建一个完全图消除商品种类的影响。

　　然后就可以愉快地0/1分数规划了。

注意：1.零环也是合法的！

　　　2.！！！1点没有什么特殊的，spfa里不能只从1点走。应该把所有点都先加进队列里！图的连通性可能很差，但只要随便有个正环就行了，故应如此！

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=105,M=9905,K=1005;const ll INF=72340172838076673;//memset 1int n,m,k,ct[N];ll t[N][N],c[N][N],s[2][N][K],dis[N],l,r,ans;bool vis[N];int rdn(){    int ret=0,fx=1;char ch=getchar();    while(ch>'9'||ch<'0'){
   if(ch=='-')fx=-1;ch=getchar();}    while(ch<='9'&&ch>='0')(ret*=10)+=ch-'0',ch=getchar();    return ret*fx;}ll rdl(){    ll ret=0,fx=1;char ch=getchar();    while(ch>'9'||ch<'0'){
   if(ch=='-')fx=-1;ch=getchar();}    while(ch<='9'&&ch>='0')(ret*=10)+=ch-'0',ch=getchar();    return ret*fx;}void floyd(){    for(int u=1;u<=n;u++)        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)                t[i][j]=min(t[i][j],t[i][u]+t[u][j]);}ll cal(int x,int y,ll lm){    return c[x][y]-t[x][y]*lm;}bool spfa(ll lm){    queue
         
           q;    for(int i=1;i<=n;i++)q.push(i),dis[i]=0,vis[i]=ct[i]=1;//从1点不一定走到所有点(1点啥也不是)    while(q.size())    {        int u=q.front();q.pop();vis[u]=0;        for(int v=1;v<=n;v++)            if(dis[v]<=dis[u]+cal(u,v,lm))//<=，因为零环也可以             {                dis[v]=dis[u]+cal(u,v,lm);                if(!vis[v])                {                    q.push(v);ct[v]++;vis[v]=1;//vis[v]=1!!(别忘写……)                    if(ct[v]>n)return true;                }            }    }    return false;}int main(){    n=rdn();m=rdn();k=rdn();int x,y;ll z;    for(int i=1;i<=n;i++)for(int u=1;u<=k;u++)        for(int d=0;d<=1;d++)        {            s[d][i][u]=rdl();            if(s[d][i][u]==-1){
   if(!d)s[d][i][u]=INF;else s[d][i][u]=-INF;}        }    memset(t,1,sizeof t);//c初值为0     for(int i=1;i<=m;i++)    {        x=rdn();y=rdn();z=rdl();t[x][y]=z;    }    floyd();    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)//        if(i!=j&&t[i][j]
          
           >1); if(spfa(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%lld",ans); return 0;}