bzoj4898:[Apio2017]商旅(分数规划+floyd+spfa)

Author Avatar
Sakits 4月 13, 2018

题解

  写的人好少,随便写写就rk3了,其实卡卡rk1应该不是问题… 在WA的边缘试探了一下二分边界,只能跑到rk22,常数不想卡了233233
  显然分数规划…直接把背包的物品塞进状态跑spfa显然是会TLE的,考虑怎么优化。
  发现nn100100,这难道不是floyd的经典范围?233233
  实际上spfa每次跑的时候可以强制某两个端点一个买一个卖来转移,中途路径肯定是走最短路啦。所以预处理出两个点买卖收益最大的物品,floyd跑出两点的最短距离之后,spfa就可以直接跑了,判一下图里有没有非负环即可,复杂度O(n2k+n3logv)O(n^2k+n^3logv)

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=110, maxk=1010, inf=1e9;
int n, m, K, x, y;
int len[maxn][maxn], val[maxn][maxn], dist[maxn], b[maxn][maxk], s[maxn][maxk];
bool flag, v[maxn];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 

void spfa(int x, int p)
{
	if(flag) return; v[x]=1;
	for(int i=1;i<=n;i++)
	if(i!=x && dist[i]>=dist[x]+1ll*p*len[x][i]-val[x][i])
	{
		if(flag || v[i]) {flag=1; return;}
		else dist[i]=dist[x]+1ll*p*len[x][i]-val[x][i], spfa(i, p);
	}
	v[x]=0;
}

inline bool check(int p)
{
	flag=0; for(int i=1;i<=n;i++) dist[i]=0, v[i]=0;
	for(int i=1;i<=n && !flag;i++) spfa(i, p);
	return flag; 
}

int main()
{
	read(n); read(m); read(K);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=K;j++)
		read(b[i][j]), read(s[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=K;k++)
			if(~s[j][k] && ~b[i][k])
			val[i][j]=max(val[i][j], s[j][k]-b[i][k]);
		}
	}
	memset(len, 32, sizeof(len));
	for(int i=1;i<=m;i++) read(x), read(y), read(len[x][y]);
	for(int k=1;k<=n;k++)	
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			len[i][j]=min(len[i][j], len[i][k]+len[k][j]);
		}
	}	
	int l=0, r=1000;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n", l);
}