分层图
受 AcWing 340.通讯线路 题目的启发,该题也可以转化为分层图最“短”路问题(在本题中是最长路)。
通讯线路题解中大佬已经对分层图进行了介绍,这里就不赘述了。
题意:从A点买入、B点卖出的最大收益
题解:
- 建立三层图。
- 每层中各节点之间的边权为0,表示连通性。
- 1层与2层之间边权为价格的相反数,表示买入。为单向边。
- 2层与3层之间边权为价值,表示卖出。为单向边。
- 使用SPFA计算从1号点到n号点的边权和的最大值。
- from fy1234567ok
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=100000*3+10, M=100000*2*10;
int h[N],e[M],ne[M],w[M],idx;
int dis[N];
bool st[N];
int n,m;
void add(int a,int b,int c=0){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){
memset(dis,-0x3f,sizeof dis);
queue<int>q;
q.push(1);
st[1]=true;
dis[1]=0;
while(q.size()){
int t=q.front(); q.pop(); st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(dis[j]<dis[t]+w[i]){
dis[j]=dis[t]+w[i];
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int c; cin>>c;
add(i,i+n,-c), add(i+n,i+2*n,c);
}
for(int i=1;i<=m;i++){
int x,y,z; cin>>x>>y>>z;
if(z==1){
add(x,y), add(x+n,y+n), add(x+2*n,y+2*n);
}
else{
add(x,y), add(x+n,y+n), add(x+2*n,y+2*n);
add(y,x), add(y+n,x+n), add(y+2*n,x+2*n);
}
}
spfa();
cout<<dis[3*n]<<endl;
return 0;
}
tql%%%
太牛了吧
這個非常好理解
狂
强啊强啊%%%%%
这个很清楚!
%%%
%%%
太妙了%%%%%
学到了 好思路
这样建图最大值一定在第三层
分层图被你们玩花了
太妙了%%%