icontofig | 发布于 2019-07-03 02:49:37 | 阅读量 101 | 最短路 分层图
发布于 2019-07-03 02:49:37 | 最短路 分层图

题解

这题其实有好几种做法,听说还有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;
bool vis[maxn*3];
void spfa(int s,int t){
	queue<int>q;
	for(int i = s;i <= t;++i)
		d[i] = -INF;
	d[s] = 0;
	vis[s] = 1;
	q.push(s);
	while(!q.empty()){
		int x = q.front();
		vis[x] = 0;
		q.pop();
		for(int i = h[x];i != -1;i = e[i].next){
			int v = e[i].to;
			if(d[v] < d[x] + e[i].dis){
				d[v] = d[x] + e[i].dis;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return;
}
int n,m;
int x,y,c;
int main(){
	memset(h,-1,sizeof(h));
	n = get_num();
	m = get_num();
	for(int i = 1;i <= n;++i)
		a[i] = get_num();
	T = 3 * n + 1;
	for(int i = 1;i <= m;++i){
		x = get_num();
		y = get_num();
		c = get_num();
		for(int j = 0;j < 3;++j){
			add(x+j*n,y+j*n,0);
			if(c == 2)add(y+j*n,x+j*n,0);
		}
	}
	for(int i = 1;i <= n;++i){
		add(i,i+n,-a[i]);
		add(i+n,i+2*n,a[i]);
	}
	for(int i = 0;i <= 2;++i)
		add(n+i*n,T,0);
	spfa(1,T);
	printf("%d\n",d[T]);
	return 0;
}

 


内容更新于: 2019-07-03 17:32:18
链接地址: http://blog.leanote.com/post/icontofig/0c575d305a7d

上一篇: 洛谷P1344 [USACO4.4]追查坏牛奶Pollutant Control 基础最小割模型

下一篇: 洛谷P1119 灾后重建 Floyd + 按时间更新

101 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航