如何给自己的公司做网站,网站模版 免费下载,文章网建站,第一模板ppt网最优贸易
题目描述 C C C 国有 n n n 个大城市和 m m m 条道路#xff0c;每条道路连接这 n n n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m m m 条道路中有一部分为单向通行的道路#xff0c;一部分为双向通行的道路#xff0c;双向通行的…最优贸易
题目描述 C C C 国有 n n n 个大城市和 m m m 条道路每条道路连接这 n n n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m m m 条道路中有一部分为单向通行的道路一部分为双向通行的道路双向通行的道路在统计条数时也计为 1 1 1 条。 C C C 国幅员辽阔各地的资源分布情况各不相同这就导致了同一种商品在不同城市的价格不一定相同。但是同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C C C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后便决定在旅游的同时利用商品在不同城市中的差价赚回一点旅费。设 C C C 国 n n n 个城市的标号从 1 ∼ n 1\sim n 1∼n阿龙决定从 1 1 1 号城市出发并最终在 n n n 号城市结束自己的旅行。在旅游的过程中任何城市可以重复经过多次但不要求经过所有 n n n 个城市。阿龙通过这样的贸易方式赚取旅费他会选择一个经过的城市买入他最喜欢的商品――水晶球并在之后经过的另一个城市卖出这个水晶球用赚取的差价当做旅费。由于阿龙主要是来 C C C 国旅游他决定这个贸易只进行最多一次当然在赚不到差价的情况下他就无需进行贸易。
假设 C C C 国有 5 5 5 个大城市城市的编号和道路连接情况如下图单向箭头表示这条道路为单向通行双向箭头表示这条道路为双向通行。 假设 1 ∼ n 1\sim n 1∼n 号城市的水晶球价格分别为 4 , 3 , 5 , 6 , 1 4,3,5,6,1 4,3,5,6,1。
阿龙可以选择如下一条线路 1 → 2 → 3 → 5 1\to2\to3\to5 1→2→3→5并在 2 2 2 号城市以 3 3 3 的价格买入水晶球在 3 3 3 号城市以 5 5 5 的价格卖出水晶球赚取的旅费数为 2 2 2。
阿龙也可以选择如下一条线路 1 → 4 → 5 → 4 → 5 1\to4\to5\to4\to5 1→4→5→4→5并在第 1 1 1 次到达 5 5 5 号城市时以 1 1 1 的价格买入水晶球在第 2 2 2 次到达 4 4 4 号城市时以 6 6 6 的价格卖出水晶球赚取的旅费数为 5 5 5。
现在给出 n n n 个城市的水晶球价格 m m m 条道路的信息每条道路所连接的两个城市的编号以及该条道路的通行情况。请你告诉阿龙他最多能赚取多少旅费。
输入格式
第一行包含 2 2 2 个正整数 n n n 和 m m m中间用一个空格隔开分别表示城市的数目和道路的数目。
第二行 n n n 个正整数每两个整数之间用一个空格隔开按标号顺序分别表示这 n n n 个城市的商品价格。
接下来 m m m 行每行有 3 3 3 个正整数 x , y , z x,y,z x,y,z每两个整数之间用一个空格隔开。如果 z 1 z1 z1表示这条道路是城市 x x x 到城市 y y y 之间的单向道路如果 z 2 z2 z2表示这条道路为城市 x x x 和城市 y y y 之间的双向道路。
输出格式
一个整数表示最多能赚取的旅费。如果没有进行贸易则输出 0 0 0。
样例 #1
样例输入 #1
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2样例输出 #1
5提示
【数据范围】
输入数据保证 1 1 1 号城市可以到达 n n n 号城市。
对于 10 % 10\% 10% 的数据 1 ≤ n ≤ 6 1\leq n\leq 6 1≤n≤6。
对于 30 % 30\% 30% 的数据 1 ≤ n ≤ 100 1\leq n\leq 100 1≤n≤100。
对于 50 % 50\% 50% 的数据不存在一条旅游路线可以从一个城市出发再回到这个城市。
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 100000 1\leq n\leq 100000 1≤n≤100000 1 ≤ m ≤ 500000 1\leq m\leq 500000 1≤m≤500000 1 ≤ x , y ≤ n 1\leq x,y\leq n 1≤x,y≤n 1 ≤ z ≤ 2 1\leq z\leq 2 1≤z≤2$1\leq $ 各城市的编号 ≤ n \leq n ≤n。
水晶球价格 ≤ 100 \leq 100 ≤100。
思路一
考虑分层图因为每个点有两种状态为买入和卖出所以我们可以建三层图平行层之间的边权为0从第一层到 第二层由当前点 u u u向 u n un un连一条边表示买入边权为 − w -w −w同理我们由 u n un un向 u n ∗ 2 un*2 un∗2连一条价值为 w w w的边表示卖出。然后对整个图去跑最长路即可(因为题目说要价值最大
#include bits/stdc.husing namespace std;
const int N 1e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nint n,m;vectorpll e[N];void add(int u,int v,int w)
{e[u].push_back({v,w});
}int st[N];
int d[N];
void spfa()
{memset(d,0x3f,sizeof(d));d[1]0;queueint q;q.push(1);st[1]1;while(!q.empty()){int tq.front();q.pop();st[t]0;int i;for(auto v:e[t]){int bv.first;int wv.second;if(d[b]d[t]w){d[b]d[t]w;if(!st[b]){q.push(b);st[b]1;}}}}
}void solve()
{cinnm;vectorint a(n5);for(int i1;in;i) cina[i],add(i,in,-a[i]),add(in,i2*n,a[i]);for(int i1;im;i){int x,y,z;cinxyz;add(x,y,0);add(xn,yn,0);add(xn*2,yn*2,0);if(z2){add(y,x,0);add(yn,xn,0);add(yn*2,xn*2,0);}}spfa();coutd[n]endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}思路二
强连通分量缩点然后进行dp。 初始想法我们考虑若其为DAG,那么我们可以直接进行DP但又因为肯定存在环所以可以对其进行强连通分量缩点。
因为缩完点后为DAG即有向无环图而我们对于有向无环图可以直接进行dp同时我们还可以知道每个强连通分量的最小价值和最大价值那么我们用dp处理出从 1 号点开始能到达所有点的最小买入价值然后用该点的卖出价值减去买入价值最后对其取max即可。
#include bits/stdc.husing namespace std;
const int N 1e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
// const int maxv 4e6 5;
// #define endl \n
int n, m, tot, dfsn[N], ins[N], low[N];
stackint s;
vectorint e[N], e2[N],e3[N];//分别用来存初始图缩点后的图缩点后的图对应的反图
vectorvectorint scc;
vectorint b(N);
int a[N];
int minv[N],maxv[N];struct node
{int u,v,z;
}h[N];void dfs(int x)
{low[x] dfsn[x] tot, ins[x] 1, s.push(x);for (auto u : e[x]){if (!dfsn[u]){dfs(u);low[x] min(low[x], low[u]);}else if (ins[u])low[x] min(low[x], dfsn[u]);}if (dfsn[x] low[x]){vectorint c;while (1){auto t s.top();c.push_back(t);ins[t] 0;s.pop();b[t] scc.size();int szscc.size();minv[sz]min(minv[sz],a[t]);maxv[sz]max(maxv[sz],a[t]);if (t x)break;}scc.push_back(c);}
}void add(int u, int v)
{e[u].push_back(v);
}bool vis[N];void dfs2(int x)
{vis[x]1;for(auto u: e3[x])if(!vis[u]) dfs2(u);
}void solve()
{cinnm;for(int i1;in;i) cina[i];for(int i1;im;i){int u,v,z;cinuvz;h[i]{u,v,z};add(u,v);if(z2) add(v,u);}memset(minv,0x3f,sizeof minv);for(int i1;in;i){if(!dfsn[i]){dfs(i);}}//缩点过程for(int i1;im;i){auto [u,v,z]h[i];int xb[u],yb[v];if(x!y) {e2[x].push_back(y),e3[y].push_back(x);if(z2) e2[y].push_back(x),e3[x].push_back(y);//同时注意因为题目中说存在双向边所以在缩点后的建图中同样也需要建立}}vectorint dp(n5);for(int i0;iscc.size();i) dp[i]minv[i];int stb[1];int edb[n];dfs2(ed);//因为要确保能到达n点所以从n开始进行dfs搜索能够到达的点由此需要缩点后的反图int ans0;for(int ist;i0;i--){//从1号点开始强连通分量即为逆拓扑序if(vis[i]) {ansmax(ans,maxv[i]-dp[i]);}for(auto u: e2[i]){dp[u]min(dp[u],dp[i]);}}coutansendl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
