题目链接: https://www.luogu.com.cn/problem/P1073.
C 国有 n n n 个大城市和 m mm 条道路, 每条道路连接这 nnn 个城市中的某两个城市. 任意两个城市之间最多只有一条道路直接相连. 这 mmm 条道路中有一部分为单向通行的道路, 一部分为双向通行的道路, 双向通行的道路在统计条数时也计为 11 1 条.
CC C 国幅员辽阔, 各地的资源分布情况各不相同, 这就导致了同一种商品在不同城市的价格不一定相同. 但是, 同一种商品在同一个城市的买入价和卖出价始终是相同的.
商人阿龙来到 CCC 国旅游. 当他得知同一种商品在不同城市的价格可能会不同这一信息之后, 便决定在旅游的同时, 利用商品在不同城市中的差价赚回一点旅费. 设 CCC 国 n 个城市的标号从 1 n1~ n1n, 阿龙决定从 11 1 号城市出发, 并最终在 nnn 号城市结束自己的旅行. 在旅游的过程中, 任何城市可以重复经过多次, 但不要求经过所有 nnn 个城市. 阿龙通过这样的贸易方式赚取旅费: 他会选择一个经过的城市买入他最喜欢的商品――水晶球, 并在之后经过的另一个城市卖出这个水晶球, 用赚取的差价当做旅费. 由于阿龙主要是来 CCC 国旅游, 他决定这个贸易只进行最多一次, 当然, 在赚不到差价的情况下他就无需进行贸易.
方法:
此题好多方法可解. 比如 2*SPFA, 分层图 + SPFA.
此文主要用 tarjan+dp.
- $minp[v]=min(minp[v],minp[u])$
- $dp[v]=max(dp[v],max(dp[u],maxp[v]-minp[v]))$
- Code:
- #include <bits/stdc++.h>
- # define LL long long
- using namespace std;
- const int maxn=100000+10;
- const int maxm=500000+10;
- int n,m;
- int price[maxn];
- struct Edge{
- int to,next;
- };
- Edge e[maxm<<1];
- int head[maxn];
- int en;
- Edge e1[maxm<<1]; // 缩点后新图
- int head1[maxn];
- int en1;
- //tarjan 组员
- int dict[maxn],low[maxn];
- int instack[maxn];
- stack<int> stk;
- int color;
- int col[maxn];
- int maxp[maxn]; // 一个 scc 中的最大价值
- int minp[maxn]; // 一个 scc 中的最小价值
- int timer;
- //dp 组员
- int indegree[maxn];
- int dp[maxn];
- queue<int> q;
- void add(int from, int to){
- e[en].next=head[from];
- e[en].to=to;
- head[from]=en;
- ++en;
- }
- void add1(int from, int to){
- e1[en1].next=head1[from];
- e1[en1].to=to;
- head1[from]=en1;
- ++en1;
- }
- void tarjan(int u){
- instack[u]=1;
- stk.push(u);
- ++timer;
- dict[u]=low[u]=timer;
- for(int i=head[u];i!=-1;i=e[i].next){
- int v=e[i].to;
- if(dict[v]==-1){
- tarjan(v);
- low[u]=min(low[u],low[v]);
- }else{
- if(instack[v]){
- low[u]=min(low[u],dict[v]);
- }
- }
- }
- if(low[u]==dict[u]){
- ++color;
- while(stk.top()!=u){
- int t=stk.top();
- stk.pop();
- instack[t]=0;
- col[t]=color;
- maxp[color]=max(maxp[color],price[t]);
- minp[color]=min(minp[color],price[t]);
- }
- stk.pop();
- instack[u]=0;
- col[u]=color;
- maxp[color]=max(maxp[color],price[u]);
- minp[color]=min(minp[color],price[u]);
- }
- }
- int helper(){
- int start=col[1];
- dp[start]=max(0,maxp[start]-minp[start]);
- q.push(start);
- while(!q.empty()){
- int u=q.front();
- q.pop();
- for(int i=head1[u];i!=-1;i=e1[i].next){
- int v=e1[i].to;
- minp[v]=min(minp[v],minp[u]);
- dp[v]=max(dp[v],max(dp[u],maxp[v]-minp[v]));
- indegree[v]--;
- if(indegree[v]==0){
- q.push(v);
- }
- }
- }
- return dp[col[n]];
- }
- int main(){
- memset(head,-1,sizeof(head));
- memset(head1,-1,sizeof(head1));
- scanf("%d %d", &n, &m);
- for(int i=1;i<=n;++i){
- scanf("%d", price+i);
- }
- for(int i=1;i<=m;++i){
- int a, b, c;
- scanf("%d %d %d", &a, &b, &c);
- add(a,b);
- if(c==2){
- add(b,a);
- }
- }
- memset(dict,-1,sizeof(dict));
- memset(minp,127,sizeof(minp));
- tarjan(1);
- vector<set<int>> nadj(color+1);
- for(int i=1;i<=n;++i){
- if(dict[i]==-1) continue; // 筛掉从 1 不可到的点
- for(int j=head[i];j!=-1;j=e[j].next){
- int v=e[j].to;
- if(dict[v]==-1) continue; // 筛掉从 1 不可到的点
- int nu=col[i];
- int nv=col[v];
- if(nu==nv) continue;
- if(nadj[nu].find(nv)==nadj[nu].end()){
- nadj[nu].insert(nv);
- add1(nu,nv);
- indegree[nv]++;
- }
- }
- }
- int res=helper();
- printf("%d", res);
- }
来源: http://www.bubuko.com/infodetail-3399375.html