做dw网站图片怎么下载,连云港市城乡建设管理局网站,网站系统繁忙是什么意思,网站建设教学视频百度云盘https://www.luogu.org/problemnew/show/P1073 C国有 n n个大城市和 mm 条道路#xff0c;每条道路连接这 nn个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mm 条道路中有一部分为单向通行的道路#xff0c;一部分为双向通行的道路#xff0c;双向通… https://www.luogu.org/problemnew/show/P1073 C国有 n n个大城市和 mm 条道路每条道路连接这 nn个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mm 条道路中有一部分为单向通行的道路一部分为双向通行的道路双向通行的道路在统计条数时也计为 1 1条。C C国幅员辽阔各地的资源分布情况各不相同这就导致了同一种商品在不同城市的价格不一定相同。但是同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 CC 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后便决定在旅游的同时利用商品在不同城市中的差价赚回一点旅费。设 CC 国 n 个城市的标号从 1~ n1 n阿龙决定从 1 1号城市出发并最终在 nn 号城市结束自己的旅行。在旅游的过程中任何城市可以重复经过多次但不要求经过所有 nn 个城市。阿龙通过这样的贸易方式赚取旅费他会选择一个经过的城市买入他最喜欢的商品――水晶球并在之后经过的另一个城市卖出这个水晶球用赚取的差价当做旅费。由于阿龙主要是来 CC 国旅游他决定这个贸易只进行最多一次当然在赚不到差价的情况下他就无需进行贸易。假设 C C国有 55个大城市城市的编号和道路连接情况如下图单向箭头表示这条道路为单向通行双向箭头表示这条道路为双向通行。假设 1~n1 n 号城市的水晶球价格分别为 4,3,5,6,14,3,5,6,1。阿龙可以选择如下一条线路11-22-33-55并在 2 2号城市以 33 的价格买入水晶球在 33号城市以 5 5的价格卖出水晶球赚取的旅费数为 2。阿龙也可以选择如下一条线路 11-44-55-44-55并在第1 1次到达 55 号城市时以 1 1的价格买入水晶球在第 22 次到达 44 号城市时以 66 的价格卖出水晶球赚取的旅费数为 55。现在给出 n n个城市的水晶球价格mm 条道路的信息每条道路所连接的两个城市的编号以及该条道路的通行情况。请你告诉阿龙他最多能赚取多少旅费。 题意 第一眼看觉得是先缩点然后DAG图上跑一边拓扑排序除了敲起来手有点酸之外没有什么难度。就直接过了。 #include map
#include set
#include ctime
#include cmath
#include queue
#include stack
#include vector
#include string
#include cstdio
#include cstdlib
#include cstring
#include sstream
#include iostream
#include algorithm
#include functional
using namespace std;
#define For(i, x, y) for(int ix;iy;i)
#define _For(i, x, y) for(int ix;iy;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf(%d, x)
#define Sca2(x,y) scanf(%d%d,x,y)
#define Sca3(x,y,z) scanf(%d%d%d,x,y,z)
#define Scl(x) scanf(%lld,x);
#define Pri(x) printf(%d\n, x)
#define Prl(x) printf(%lld\n,x);
#define CLR(u) for(int i0;iN;i)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pairint,int
#define PIL pairint,long long
#define PLL pairlong long,long long
#define pb push_back
#define fi first
#define se second
typedef vectorint VI;
int read(){int x 0,f 1;char c getchar();while (c0 || c9){if (c -) f -1;c getchar();}
while (c 0c 9){x x * 10 c - 0;c getchar();}return x*f;}
const double eps 1e-9;
const int maxn 1e5 10;
const int maxm 5e5 10;
const int INF 0x3f3f3f3f;
const int mod 1e9 7;
int N,M,K;
int val[maxn];
struct Edge{int to,next;
}edge[maxm * 2];
int head[maxn],tot;
void init(){for(int i 0 ; i N 1; i ) head[i] -1;tot 0;
}
void add(int u,int v){edge[tot].to v;edge[tot].next head[u];head[u] tot;
}
int Low[maxn],dfn[maxn],Stack[maxn],Belong[maxn],num[maxn];
int Index,top,scc;
bool Instack[maxn];
void Tarjan(int u){int v;Low[u] dfn[u] Index;Stack[top] u;Instack[u] true;for(int i head[u]; ~i; i edge[i].next){v edge[i].to;if(!dfn[v]){Tarjan(v);if(Low[u] Low[v]) Low[u] Low[v];}else if(Instack[v] Low[u] dfn[v]){Low[u] dfn[v];}}if(Low[u] dfn[u]){scc;do{v Stack[--top];Instack[v] false;Belong[v] scc;num[scc];}while(v ! u);}
}
int MAX[maxn],MIN[maxn],ind[maxn],ans[maxn];
vectorintP[maxn];
int main(){Sca2(N,M); init();for(int i 1; i N ; i ) Sca(val[i]);for(int i 1; i M ; i ){int u,v,w; Sca3(u,v,w);add(u,v);if(w 2) add(v,u);}for(int i 1; i N ; i ) if(!dfn[i]) Tarjan(i);for(int i 1; i scc; i ){MAX[i] -INF; MIN[i] INF;}for(int i 1; i N ; i ){int u Belong[i];MAX[u] max(MAX[u],val[i]);MIN[u] min(MIN[u],val[i]);for(int j head[i]; ~j; j edge[j].next){int v Belong[edge[j].to];if(u v) continue;P[u].push_back(v);ind[v]; }}queueintQ;for(int i 1; i scc; i ) if(!ind[i]) Q.push(i);while(!Q.empty()){int u Q.front(); Q.pop();ans[u] max(ans[u],MAX[u] - MIN[u]);for(int i 0; i P[u].size(); i ){int v P[u][i];ind[v]--;MIN[v] min(MIN[v],MIN[u]);ans[v] max(ans[v],ans[u]);if(!ind[v]) Q.push(v);}}Pri(ans[Belong[N]]);return 0;
} 缩点 拓扑排序 后来发现还有一种更加新奇的解法构造分层图将原图变为一个带权图权的意思是商人走这条路要得到的钱负数代表花费一开始的图所有边权都是0表示这个商人什么也不买走来走去不亏也不赚。然后我们对于每个点v构造一条边通向v N,边权为-val[v],表示商人在这个点买了一个水晶球1 N ~ N N就是出现的第二个图对于第二图也像第一条路一样构造出相同的边权为0的边表示商人买了水晶球之后依然可以不买也不卖的在这个图上走来走去同理我们再v N ~ v N N构造一条边权为val[v]的边表示商人买完之后在这个点又卖出去了同第二个图一样构造出第三个图最后题意要求到达终点所以可取的点只有N和3 * N,即第一个图和第三个图的终点跑一边最短长路即可。 由于边权有正有负的不能用Dijkstra跑无向图也不可以拓扑排序dp所以只能SPFA大概是这个做法的唯一缺点 #include map
#include set
#include ctime
#include cmath
#include queue
#include stack
#include vector
#include string
#include cstdio
#include cstdlib
#include cstring
#include sstream
#include iostream
#include algorithm
#include functional
using namespace std;
#define For(i, x, y) for(int ix;iy;i)
#define _For(i, x, y) for(int ix;iy;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf(%d, x)
#define Sca2(x,y) scanf(%d%d,x,y)
#define Sca3(x,y,z) scanf(%d%d%d,x,y,z)
#define Scl(x) scanf(%lld,x);
#define Pri(x) printf(%d\n, x)
#define Prl(x) printf(%lld\n,x);
#define CLR(u) for(int i0;iN;i)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pairint,int
#define PIL pairint,long long
#define PLL pairlong long,long long
#define pb push_back
#define fi first
#define se second
typedef vectorint VI;
int read(){int x 0,f 1;char c getchar();while (c0 || c9){if (c -) f -1;c getchar();}
while (c 0c 9){x x * 10 c - 0;c getchar();}return x*f;}
const double eps 1e-9;
const int maxn 3e5 10;
const int maxm 2e6 10;
const int INF 0x3f3f3f3f;
const int mod 1e9 7;
int N,M,K;
int head[maxn],tot;
struct Edge{int to,next,dis;
}edge[maxm];
void init(){for(int i 0 ; i 3 * N 1; i ) head[i] -1;tot 0;
}
void add(int u,int v,int w){edge[tot].to v;edge[tot].next head[u];edge[tot].dis w;head[u] tot;
}
int val[maxn];
int dis[maxn],vis[maxn];
int SPFA(int s,int t){for(int i 0 ; i 3 * N 1; i ) dis[i] -INF;dis[1] 0;queueintQ;Q.push(s);while(!Q.empty()){int u Q.front(); Q.pop();vis[u] 0;for(int i head[u]; ~i ; i edge[i].next){int v edge[i].to;if(dis[v] dis[u] edge[i].dis){dis[v] dis[u] edge[i].dis;if(!vis[v]){vis[v] 1;Q.push(v);}}} }if(dis[t] -INF) dis[t] 0;return dis[t];
}
int main(){Sca2(N,M); init();for(int i 1; i N ; i ){Sca(val[i]);add(i,i N,-val[i]);add(i N,i N N,val[i]);} for(int i 1; i M ; i ){int u,v,w; Sca3(u,v,w);add(u,v,0);add(u N,v N,0);add(u N N,v N N,0);if(w 2){add(v,u,0);add(v N,u N,0);add(v N,u N N,0);} }int t 3 * N 1,s 1;add(N,t,0); add(3 * N,t,0);Pri(SPFA(s,t));return 0;
} 转载于:https://www.cnblogs.com/Hugh-Locke/p/10330356.html
