洛谷p1073 最优贸易

链接

首先易得暴n²的暴力，暴力枚举就行

显然1e5的数据是会炸的

我们再分析题意，发现一共分为两个个步骤，也可以说是状态，即在一个点买入，在另一个点卖出，我们可以构建一个三层分层图

第一层的每个点和第二层的对应点各连接一条权值为-val[i]（val[i]表示i号点的水晶价格）的单向边

表示在i号点买进，

再在第二层的每个点向第三层的对应点各连接一条权值为val[j]的有向边

表示在j号点卖出，

构建好分层图后

我们在分层图上跑最长路

以第三层中的n号点为终点

便可求解

即使有负权，可我们因为跑的是最长路

所以dijistla不受影响

ac代码如下

时间复杂度边为3mlog3m

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<queue>

#define inf -0x3f3f3f3f

using namespace std;

const int maxn=5e5;

inline int read(){

	int ret=0;

	int f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')

			f=-f;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9'){

		ret=ret*10+(ch^'0');

		ch=getchar();

	}

	return f*ret;

}

struct edge{

	int nex;

	int to;

	int v;

}e[maxn*3];

struct node{

	int u,d;

	bool operator <(const node &x) const{

		return x.d<d;

	}

};

int head[maxn*3];

int cnt;

void add(int u,int to,int v){

	cnt++;

	e[cnt].nex=head[u];

	e[cnt].to=to;

	e[cnt].v=v;

	head[u]=cnt;

}

int n,m;

int dis[maxn*3];

int val[maxn];

inline void di(int s){

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

		dis[i]=inf;

	}

	dis[s]=0;

	priority_queue<node>q;

	q.push((node){s,0});

	while(!q.empty()){

		node f=q.top();

		q.pop();

		int u=f.u;

		int d=f.d;

		if(dis[u]!=d)

			continue;

		for(int i=head[u];i;i=e[i].nex){

			int v=e[i].v;

			int y=e[i].to;

			if(dis[u]+v>dis[y]){

				dis[y]=dis[u]+v;

				q.push((node){y,dis[y]});

			}

		}

	}

}

int main(){

//	freopen("a.in","r",stdin);

	n=read();

	m=read();

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

		val[i]=read();

		add(i,i+n,-val[i]);

		add(i+n,+2*n+i,val[i]);

	}

	int x,y,z;

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

		x=read();

		y=read();

		z=read();

		add(x,y,0);

		add(x+n,y+n,0);

		add(x+2*n,y+2*n,0);

		if(z==2){

			add(y,x,0);

			add(y+n,x+n,0);

			add(y+2*n,x+2*n,0);

		}

	}

	n=n*3;

	di(1);

	cout<<dis[n];

	return 0;

}

结束喽！

巴特西

P1073 最优贸易分层图+最长路

洛谷p1073 最优贸易

链接

最新文章

热门文章

巴特西

P1073 最优贸易 分层图+最长路

洛谷p1073 最优贸易

链接

最新文章

热门文章

P1073 最优贸易分层图+最长路