图论习题2

[刷题记录]图论习题2（最短路综合应用）

• 图论中最短路算法（包括$SPFA$和$Dijkstra$）的一部分基础习题，也结合了许多其他知识点，如$dp$、贪心等

Vijos P1635 城市链接

题意

• 简化：给一个有向有权图，要求输出最短路径经过的点和最短路长度

题解

• 裸一个$SPFA$或者$Dijkstra$，开一个$pre$数组在每次节点更新时记录一下（记录方式为$pre[v]=u$，意思是记录每一个节点的前驱），最后从$pre[n]$倒序拷贝到一个数组里然后顺序输出即可

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
struct Edge{
	int u,v,w,next;
}e[1000005];

struct node{
	int u,dis;
	bool operator<(const node& rhs)const{
		return dis>rhs.dis;
	}
};

int n,s=1,cnt,head[1000005],pre[1000005],ans[1000005];
inline void addedge(int u,int v,int w){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int dis[1000005];
inline void dijkstra(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	priority_queue<node> q;
	dis[s]=0;
	q.push(node{s,0});
	while(!q.empty()){
		node q1=q.top();
		q.pop();
		int u=q1.u,d=q1.dis;
		if(d>dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]=u;
				q.push(node{v,dis[v]});
			}
		}
	}
	int t=0;
	for(int i=n;i;i=pre[i]){
		ans[++t]=i;
	}
	for(int i=t;i>=1;i--) cout<<ans[i]<<" ";
}


int main(){
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>x;
			if(x!=0) addedge(i,j,x);
		}
	}
	dijkstra();
	cout<<endl;
	cout<<dis[n]<<endl;
	return 0;
	
}//https://vijos.org/p/1635

NOIP 2009 提高组 T3 最优贸易

题意

• 简化：给一个有向无权图，每个节点有一个数值（代表商品价格），现在有一个商人从起点经过若干点（可重复经过）到达终点，途中可以选择一个点的价格买入商品，再在之后经过的某一个卖出商品（买入卖出操作只能有一次），问最大利润是多少？

题解

• 题目的意思很清楚了，就是要求你从起点出发到一个点以价格1买入，再到这个点之后以价格2卖出，求这两个价格的最大差值
• 我们可以想到$SPFA$，它可以求出从起点到每一个点的最短路，那么这里是无权图，所以我们的“最短”可以定义为节点的价格最小，这样过一遍$SPFA$就可以求出到达每个节点买入价格的最小值
• 还剩下从每一个节点到所有之后的节点的最大值，怎么求呢？
• 逆向思维：我们从该点出发往下一个点走，就相当于下一个点往我们这边走，因此我们可以反向建图，再从终点开始往起点过一遍$SPFA$（但这里是求“最长”，即每个点的最大价格）就可以求出从每个点出发到终点能够卖出的最大价格

• 这样，我们已经求出了以下两部分：

  1. 从起点出发到每个点买入的最小价格
  2. 从每个点出发到终点卖出的最大价格

• 然后只需要对每个点求出这两者的最大差值即可

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
struct Edge{
	int u,v,w,next;
}e1[1000005],e2[1000005];

int n,m,s=1,cnt1,cnt2,head1[1000005],head2[1000005],jia[1000005];
inline void addedge1(int u,int v,int w){
	e1[++cnt1].u=u;
	e1[cnt1].v=v;
	e1[cnt1].w=w;
	e1[cnt1].next=head1[u];
	head1[u]=cnt1;
}
int dis1[1000005],dis2[1000005],vis1[1000005],vis2[1000005];
inline void addedge2(int u,int v,int w){
	e2[++cnt2].u=u;
	e2[cnt2].v=v;
	e2[cnt2].w=w;
	e2[cnt2].next=head2[u];
	head2[u]=cnt2;
}

inline void spfa1(){
	memset(vis1,0,sizeof(vis1));
	for(int i=1;i<=n;i++) dis1[i]=inf;
	vis1[1]=1;
	dis1[1]=jia[1];
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis1[u]=0;
		dis1[u]=min(dis1[u],jia[u]); //求每个点最小值
		for(int i=head1[u];i;i=e1[i].next){
			int v=e1[i].v;
			if(dis1[v]>dis1[u]){
				dis1[v]=dis1[u];
				if(vis1[v]==0){
					vis1[v]=1;
					q.push(v);
				}
			}
		}
	}
}

inline void spfa2(){
	memset(vis2,0,sizeof(vis2));
	for(int i=1;i<=n;i++) dis2[i]=0;
	vis2[n]=1;
	dis2[n]=jia[n];
	queue<int> q;
	q.push(n);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis2[u]=0;
		dis2[u]=max(dis2[u],jia[u]); //求每个点最大值
		for(int i=head2[u];i;i=e2[i].next){
			int v=e2[i].v;
			if(dis2[v]<dis2[u]){
				dis2[v]=dis2[u];
				if(vis2[v]==0){
					vis2[v]=1;
					q.push(v);
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>jia[i];
	for(int i=1;i<=m;i++){
		int u,v,z;
		cin>>u>>v>>z;
		addedge1(u,v,1); //正反建图
		addedge2(v,u,1);
		if(z==2){
			addedge1(v,u,1);
			addedge2(u,v,1);
		}
	}
	
	spfa1(); //正反spfa
	spfa2();
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=max(sum,dis2[i]-dis1[i]); //取最大差值
	}
	cout<<sum<<endl;
	return 0;
}//https://www.luogu.com.cn/problem/P1073

未完待续