题目：https://www.luogu.org/problemnew/show/P3778
一看就是0/1分数规划。但不能直接套模板，因为有个商品种类的限制。
考虑从a买在b卖，商品种类根本没用，关注的是最大营利。于是可以考虑暴枚建一个完全图消除商品种类的影响。
然后就可以愉快地0/1分数规划了。
注意：1.零环也是合法的！
2.！！！1点没有什么特殊的，spfa里不能只从1点走。应该把所有点都先加进队列里！图的连通性可能很差，但只要随便有个正环就行了，故应如此！
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=105,M=9905,K=1005; const ll INF=72340172838076673;//memset 1 int 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<int> 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]<INF)//写不写都行,写了更快一点//INF的t会在spfa里判掉//i与i数据应该不会给能营利的 for(int u=1;u<=k;u++)c[i][j]=max(c[i][j],s[1][j][u]-s[0][i][u]),r=max(r,c[i][j]); while(l<=r) { ll mid=((l+r)>>1); if(spfa(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%lld",ans); return 0; }