BZOJ 4898 Luogu P3778 [APIO2017]商旅 (分数规划、最短路)

题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4898

(luogu)https://www.luogu.org/problemnew/show/P3778

题解: 先Floyd求任意两点最短路。

二分答案\(mid\)之后把边权乘以\(mid\)判断是否有大于\(0\)的即可。

\(O(n^2)\)枚举每一对点，然后如果能实现从\(i\)点买入\(j\)点卖出，那么从\(i\)向\(j\)连边代价为利润减(最短路乘以\(mid\))。

然后直接在原图上SPFA判正环即可。

时间复杂度\(O(ShortestPath(n,m+n^2)+n^3+n^2k)\)

自己还想到另一种做法就是设\(dp[i][j]\)为在\(i\)点持物品为\(j\)的最大利润然后SPFA转移，没实现过。估计不可行，即使是对的也太慢。

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<algorithm>

#define llong long long

using namespace std;

const int N = 100;

const int M = 10000;

const int P = 1000;

const llong INF = 2000000000ll;

struct AEdge

{

	int u,v; llong w;

} ae[M+3];

struct Edge

{

	int v,nxt; llong w;

} e[(M<<1)+3];

llong dist[N+3];

int que[N+3];

bool inq[N+3];

int tot[N+3];

bool vis[N+3];

int fe[N+3];

llong ai[N+3][P+3],ao[N+3][P+3];

llong mxv[N+3][N+3];

llong dis[N+3][N+3];

int n,m,p,en;

void addedge(int u,int v,llong w)

{

//	printf("addedge %d %d %lld\n",u,v,w);

	en++; e[en].v = v; e[en].w = w;

	e[en].nxt = fe[u]; fe[u] = en;

}

void clear()

{

	for(int i=1; i<=n; i++) fe[i] = 0,vis[i] = false;

	for(int i=1; i<=en; i++) {e[i].v = e[i].w = e[i].nxt = 0;}

	en = 0;

}

bool spfa(int s)

{

	for(int i=1; i<=n; i++) dist[i] = -INF,tot[i] = 0,inq[i] = false;

	int head = 1,tail = 2; que[tail-1] = s; dist[s] = 0ll; inq[s] = true; tot[s] = 1; vis[s] = true;

	while(head!=tail)

	{

		int u = que[head]; head++; if(head>n+1) head = 1;

		for(int i=fe[u]; i; i=e[i].nxt)

		{

			int v = e[i].v;

			if(dist[v]<=dist[u]+e[i].w)

			{

				dist[v] = dist[u]+e[i].w;

				vis[v] = true;

				if(!inq[v])

				{

					que[tail] = v; tail++; if(tail>n+1) tail = 1;

					inq[v] = true; tot[v]++;

					if(tot[v]>n) return true;

				}

			}

		}

		inq[u] = false;

	}

	return false;

}

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dis[i][j] = INF;

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=p; j++)

		{

			scanf("%lld%lld",&ai[i][j],&ao[i][j]);

		}

	}

	for(int i=1; i<=m; i++)

	{

		scanf("%d%d%lld",&ae[i].u,&ae[i].v,&ae[i].w);

		dis[ae[i].u][ae[i].v] = ae[i].w;

	}

	for(int k=1; k<=n; k++)

	{

		for(int i=1; i<=n; i++)

		{

			for(int j=1; j<=n; j++)

			{

				dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);

			}

		}

	}

//	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) printf("dis[%d][%d]=%lld\n",i,j,dis[i][j]);

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=n; j++)

		{

			mxv[i][j] = -INF;

			if(dis[i][j])

			{

				for(int k=1; k<=p; k++)

				{

					if(ai[i][k]!=-1 && ao[j][k]!=-1) {mxv[i][j] = max(mxv[i][j],ao[j][k]-ai[i][k]);}

				}

			}

//			printf("mxv[%d][%d]=%lld\n",i,j,mxv[i][j]);

		}

	}

	llong left = 0ll,right = INF;

	while(left<right)

	{

		llong mid = (left+right+1ll)>>1;

//		printf("left%lld right%lld mid%lld\n",left,right,mid);

		for(int i=1; i<=m; i++)

		{

			addedge(ae[i].u,ae[i].v,-ae[i].w*mid);

		}

		for(int i=1; i<=n; i++)

		{

			for(int j=1; j<=n; j++)

			{

				if(mxv[i][j]>-INF) {addedge(i,j,mxv[i][j]-mid*dis[i][j]);}

			}

		}

		bool ok = false;

		for(int i=1; i<=n; i++)

		{

			if(!vis[i]) {bool cur = spfa(i); if(cur) {ok = true; break;}}

		}

		if(ok) {left = mid;}

		else {right = mid-1;}

		clear();

	}

	printf("%lld\n",left);

	return 0;

}

巴特西

BZOJ 4898 Luogu P3778 [APIO2017]商旅 (分数规划、最短路)

代码

最新文章

热门文章