北京网站建设华网天下,wordpress 火车头采集,免费算命,大连html5网站建设其实并不会分数规划 因为要最大化 ans总收益/总路程 #xff0c;所以考虑二分答案#xff0c;找到一条 ans总收益/总路程 的回路。先预处理出d(i,j)为(i,j)最短路#xff0c;w(i,j)为在i买某个物品在j卖出的最大收益#xff08;最小为0#xff09;。把式子变一下…其实并不会分数规划 因为要最大化 ans总收益/总路程 所以考虑二分答案找到一条 ans总收益/总路程 的回路。先预处理出d(i,j)为(i,j)最短路w(i,j)为在i买某个物品在j卖出的最大收益最小为0。把式子变一下据说这是分数规划套路变成ans*总路程总收益总收益-ans*总路程0。建一张新图(i,j)边权为w(i,j)-d(i,j)*ans然后用Floyd在新图中检查是否有非负环即可。 #includeiostream
#includecstdio
using namespace std;
const int N105,K1005;
const long long inf1e18;
int n,m,q;
long long b[N][K],s[N][K],d[N][N],a[N][N],c[N][N],w[N][N];
int read()
{int r0,f1;char pgetchar();while(p9||p0){if(p-)f-1;pgetchar();}while(p0p9){rr*10p-48;pgetchar();}return r*f;
}
bool ok(long long mid)
{for(int i1;in;i)for(int j1;jn;j)if(d[i][j]inf||ij)a[i][j]-inf;elsea[i][j]w[i][j]-mid*d[i][j];for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)a[i][j]max(a[i][j],a[i][k]a[k][j]);for(int i1;in;i)if(a[i][i]0)return 1;for(int i1;in;i)for(int j1;jn;j)c[i][j]a[i][j];for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)a[i][j]max(a[i][j],a[i][k]a[k][j]);for(int i1;in;i)for(int j1;jn;j)if(a[i][j]c[i][j])return 1;return 0;
}
int main()
{nread(),mread(),qread();for(int i1;in;i)for(int j1;jq;j)b[i][j]read(),s[i][j]read();for(int i1;in;i)for(int j1;jn;j)if(i!j)d[i][j]inf;for(int i1;im;i){int xread(),yread(),zread();d[x][y]min(d[x][y],(long long)z);}for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)d[i][j]min(d[i][j],d[i][k]d[k][j]);for(int i1;in;i)for(int j1;jn;j)for(int k1;kq;k)if(b[i][k]!-1s[j][k]!-1)w[i][j]max(w[i][j],s[j][k]-b[i][k]);long long ans0,l0,r1e12;while(lr){long long mid(lr)1;if(ok(mid))lmid1,ansmid;elsermid-1;}printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/lokiii/p/8793378.html
