填坑
[JLOI2011] 飞行路线 https://www.luogu.org/problem/P4568
板子题
我们可以分成 k + 1 层
每一层按照题意连边
每相邻的两层间连长度为 0 的合法有向边
比如题目给出 u -> v : w 这条边 , 那么同时可以连 u(dep1) -> v(dep2) : 0 一条边 , 表示第一层点 u 可以花费 0 到第二层点 v
这样很显然能看出 , 从一层到下一层 , 就等于是坐了一次免费的飞机
然后跑一边 Dij 就没了
- Code:
- //#pragma GCC optimize(2)
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<queue>
- #include<vector>
- #include<iostream>
- #include<algorithm>
- #define N 510
- #define debug 1
- #define osu auto
- #define FILETEST 1
- #define inf 2500010
- #define ll long long
- #define ha 998244353
- #define INF 0x7fffffff
- #define pii std::pair <int, int>
- #define INF_T 9223372036854775807
- #define APART puts("----------------------")
- #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
- namespace chino{
- inline void setting(){
- #if FILETEST
- freopen("_test.in", "r", stdin);
- freopen("_test.me.out", "w", stdout);
- #endif
- return;
- }
- inline int read(){
- register char c = getchar(), up = c; register int num = 0;
- while(c <'0' || c> '9') up = c, c = getchar();
- while(c>= '0' && c <= '9') num = (num <<3) + (num << 1) + (c ^ '0'), c = getchar();
- return up == '-' ? -num : num;
- }
- int n, m, k;
- int s, t;
- int index;
- int dis[inf], vis[inf];
- int head[inf];
- struct Edge{
- int to;
- int val;
- int next;
- }e[inf << 1];
- struct Node{
- int dis;
- int pos;
- inline bool operator<(const Node &next) const {
- return dis> next.dis;
- }
- };
- std::priority_queue <Node, std::vector <Node>> P;
- inline void AddEdge(int from, int to, int val){
- ++index;
- e[index].to = to;
- e[index].val = val;
- e[index].next = head[from];
- head[from] = index;
- return;
- }
- inline void dij(int s){
- P.push(Node{0, s});
- memset(dis, 10, sizeof dis);
- dis[s] = 0;
- while(!P.empty()){
- int x = P.top().pos; P.pop();
- if(vis[x]) continue;
- vis[x] = 1;
- for(int i = head[x]; i; i = e[i].next){
- int y = e[i].to;
- if(dis[y]> dis[x] + e[i].val){
- dis[y] = dis[x] + e[i].val;
- if(vis[y] == 0) P.push(Node{dis[y], y});
- }
- }
- }
- return;
- }
- inline int main(){
- memset(e, 0, sizeof e);
- n = read(), m = read(), k = read();
- s = read(), t = read();
- for(int i = 1; i <= m; i++){
- int u = read();
- int v = read();
- int w = read();
- for(int j = 0; j <= k; j++){
- AddEdge(u + j * n, v + j * n, w);
- AddEdge(v + j * n, u + j * n, w);
- if(j == 0) continue;
- AddEdge(u + (j - 1) * n, v + j * n, 0);
- AddEdge(v + (j - 1) * n, u + j * n, 0);
- }
- }
- dij(s);
- int ans = INF;
- for(int i = 0; i <= k; i++) // 可能并不会用光 k 次免费坐飞机的机会
- ans = std::min (ans, dis[t + i * n]);
- printf("%d\n", ans);
- return 0;
- }
- }//namespace chino
- signed main(){return chino::main();}
[NOIP2009] 最优贸易 https://www.luogu.org/problem/P1073
在买入或卖出之外的时刻是可以在图上随便游走的
所以每一层点之间的边权是 0
分三层 , 从第一层掉到第二层表示买入了 , 从第二层掉到第三层表示卖出了
所以一二层间每个点与自己连一条 -cost 的边 , 表示花费了 cost 的软妹币
二三层间自己与自己连 cost 的边 , 表示卖出从而得到了 cost 的软妹币
这样 SPFA 一遍最长路
然而有的情况可能买入卖出后得到了负收益
那这种情况显然不如不做这笔生意
- Code:
- //#pragma GCC optimize(2)
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<queue>
- #include<vector>
- #include<iostream>
- #include<algorithm>
- #define N 510
- #define debug 1
- #define osu auto
- #define FILETEST 1
- #define inf 2000010
- #define ll long long
- #define ha 998244353
- #define INF 0x7fffffff
- #define pii std::pair <int, int>
- #define INF_T 9223372036854775807
- #define APART puts("----------------------")
- #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
- namespace chino{
- inline void setting(){
- #if FILETEST
- freopen("_test.in", "r", stdin);
- freopen("_test.me.out", "w", stdout);
- #endif
- return;
- }
- inline int read(){
- register char c = getchar(), up = c; register int num = 0;
- while(c <'0' || c> '9') up = c, c = getchar();
- while(c>= '0' && c <= '9') num = (num <<3) + (num << 1) + (c ^ '0'), c = getchar();
- return up == '-' ? -num : num;
- }
- int n, m;
- int index;
- int s, t;
- int dis[inf], vis[inf];
- int cost[inf];
- int head[inf];
- struct Edge{
- int to;
- int val;
- int next;
- }e[inf << 1];
- std::queue <int> Q;
- inline void AddEdge(int from, int to, int val){
- ++index;
- e[index].to = to;
- e[index].val = val;
- e[index].next = head[from];
- head[from] = index;
- return;
- }
- inline void spfa(int s){
- std::fill(dis + 1, dis + 1 + n + n + n, -(INF>> 1));
- Q.push(s);
- dis[s] = 0, vis[s] = 1;
- while(!Q.empty()){
- int x = Q.front(); Q.pop();
- vis[x] = 0;
- for(int i = head[x]; i; i = e[i].next){
- int y = e[i].to;
- if(dis[y] < dis[x] + e[i].val){
- dis[y] = dis[x] + e[i].val;
- if(vis[y] == 0){
- vis[y] = 1;
- Q.push(y);
- }
- }
- }
- }
- return;
- }
- inline int main(){
- n = read(), m = read();
- for(int i = 1; i <= n; i++){
- cost[i] = read();
- AddEdge(i, i + n, -cost[i]);
- AddEdge(i + n, i + n + n, cost[i]);
- }
- for(int i = 1; i <= m; i++){
- int u = read();
- int v = read();
- int w = read() - 1;
- AddEdge(u, v, 0);
- AddEdge(u + n, v + n, 0);
- AddEdge(u + n + n, v + n + n, 0);
- if(w == 0) continue;
- AddEdge(v, u, 0);
- AddEdge(v + n, u + n, 0);
- AddEdge(v + n + n, u + n + n, 0);
- }
- s = 1, t = n + n + n;
- spfa(s);
- printf("%d\n", std::max (0, dis[t]));
- return 0;
- }
- }//namespace chino
- signed main(){return chino::main();}
来源: http://www.bubuko.com/infodetail-3280328.html