Tag-分层图

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-07-03 02:49:37 |  0 Comments  |  最短路 分层图

洛谷P1073 最优贸易 分层图SPFA

题解

这题其实有好几种做法,听说还有tarjan缩点+topsort+dp的做法,不过想了想真的是太恶心了……

于是换一种想法,我们可以像最小费用最大流惯用套路一样,进行拆点,把一个点的不同状态转化成不同的点。

因为只能买卖一次,这道题其实可以分作三种状态:

1.没有买入也没有卖出 2.买入了但是没卖出3.买入了并且卖出了。

按照三种方案来拆点,每个点拆成三个,于是可以把点分成这三层。

可以将每层内的点的距离认为是0距离,表示不买入也不卖出。每个点与自己下一层的对应点连有向边,表示买入或者卖出。

分成两种情况:

1.买入,第一层向第二层对应点连边,边权为当前城市水晶球价格的负值,代表花钱买入。

2.卖出,第二层向第三层对应点连边,边权为当前城市水晶球价格的正值,代表卖出。

然后建起整张图,设置一个超级汇点T,让三层上n号点对应的点与超级汇点T连0距离的边,最终跑最长路,从1号点出发到T的最长路即最多能赚取的旅费。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num<<1) + (num<<3) + c - '0';
	return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
const int maxm = 5e5+5;
struct edge{
	int to,next,dis;
}e[maxm<<4];
int h[maxn*3];
int cnt = 0;
int d[maxn*3];
int a[maxn];
int T;
void add(int u,int v,int c){
	e[cnt].to = v;e[cnt].next = h[u];e[cnt].dis = c;
	h[u] = cnt++;
	return;
}
const int INF = 1e9;
Title - Artist
0:00