标签: 最短路

[APIO2015]雅加达的摩天楼 题解

[APIO2015]雅加达的摩天楼 题解

题目地址:洛谷:【P3645】[APIO2015]雅加达的摩天楼 – 洛谷、BZOJ:Problem 4070. — [Apio2015]雅加达的摩天楼

题目描述

印尼首都雅加达市有 N 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 0 到 N−1。除了这 N 座摩天楼外,雅加达市没有其他摩天楼。
有 M 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 0 到 M−1。编号为 i 的 doge 最初居住于编号为 Bi 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 i 的 doge 的跳跃能力为 Pi (Pi>0)。
在一次跳跃中,位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p (如果 0≤b−p<N)或 b+p (如果 0≤b+p<N)的摩天楼。
编号为 0 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编 号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择:

  • 跳跃到其他摩天楼上;
  • 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到 1 号 doge。

输入输出格式

输入格式:
输入的第一行包含两个整数 N 和 M。
接下来 M 行,每行包含两个整数 Bi 和 Pi。

输出格式:
输出一行,表示所需要的最少步数。如果消息永远无法传递到 1 号 doge,输出 −1。

输入输出样例

输入样例#1:

5 3
0 2
1 1
4 1

输出样例#1:

5

说明

所有数据都保证 0≤Bi<N。
子任务 1 (10 分),1≤N≤10,1≤Pi≤10,2≤M≤3
子任务 2 (12 分),1≤N≤100,1≤Pi≤100,2≤M≤2000
子任务 3 (14 分),1≤N≤2000,1≤Pi≤2000,2≤M≤2000
子任务 4 (21 分),1≤N≤2000,1≤Pi≤2000,2≤M≤30000
子任务 5 (43 分),1≤N≤30000,1≤Pi≤30000,2≤M≤30000

题解

其实可以把这个转化成一个最短路问题,从一个有doge的建筑向它能够到的所有建筑连有向边,但是如果p太小,边的数量甚至可以达到n^2
我们考虑将p在\min(\sqrt{n}, 100)以内的点进行一个预处理,即按照枚举这些p,对于每个建筑每个p值建新点,把所有可能的边都直接建起来,并使拆出来的这些点都有出边指向这些点所在的建筑原来的点。进行了这一通预处理,对于p在上述范围内的点,只需要从它所在的建筑原点建出边指向对应的p拆出来的点即可。优化后的边数就只有n \sqrt{n}规模了。
由于vector占用空间过大,推荐使用邻接表存图。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>
#include <vector>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 30005;

int n, m;

struct Edge {
    int to, w, nxt;
} gra[MAXN * 500];
int head[MAXN * 200], tot;

inline void addedge(int u, int v, int w) {
    gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
}

int dis[MAXN * 200];
bool inque[MAXN * 200];
std::queue<int> que;

inline void spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(dis[v] > dis[u] + gra[i].w) {
                dis[v] = dis[u] + gra[i].w;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
}

int b[MAXN], p[MAXN];

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        b[i] = readint() + 1; p[i] = readint();
    }
    int sqn = std::min(int(sqrt(n)), 100);
    for(int i = 1; i <= sqn; i++) {
        for(int j = 1; j <= n; j++) {
            addedge(i * n + j, j, 0);
            if(j + i <= n) {
                addedge(i * n + j, i * n + j + i, 1);
                addedge(i * n + j + i, i * n + j, 1);
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        if(p[i] <= sqn) {
            addedge(b[i], b[i] + p[i] * n, 0);
        } else {
            for(int j = 1; b[i] + p[i] * j <= n; j++) {
                addedge(b[i], b[i] + p[i] * j, j);
            }
            for(int j = 1; b[i] - p[i] * j >= 1; j++) {
                addedge(b[i], b[i] - p[i] * j, j);
            }
        }
    }
    spfa(b[1]);
    printf("%d", dis[b[2]] == 0x3f3f3f3f ? -1 : dis[b[2]]);
    return 0;
}
[APIO2017]商旅 题解

[APIO2017]商旅 题解

题目地址:洛谷:【P3778】[APIO2017]商旅 – 洛谷、BZOJ:Problem 4898. — [Apio2017]商旅

题目描述

在广阔的澳大利亚内陆地区长途跋涉后,你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引,决定定居于此,做一个商人。科巴有个集市,集市用从1到N的整数编号,集市之间通过M条单向道路连接,通过每条道路都需要消耗一定的时间。
在科巴的集市上,有K种不同的商品,商品用从1到K的整数编号。每个集市对每种商品都有自己的定价,买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品:一个集市可能只提供部分商品的双向交易服务;对于一种商品,一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品,它收购这种商品的数量是不限的,同样,一个集市如果卖出一种商品,则它卖出这种商品的数量也是不限的。
为了更快地获得收益,你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发,沿着道路前进,经过若干个市场并最终回到出发点。在环路中,允许多次经过同一个集市或同一条道路。在经过集市时,你可以购买或者卖出商品,一旦你购买了一个商品,你需要把它装在背包里带走。由于你的背包非常小,任何时候你最多只能持有一个商品。在购买一个商品时,你不需要考虑你是否有足够的金钱,但在卖出时,需要注意只能卖出你拥有的商品。
从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱,而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效率是指从环路中得到的收益除以花费的时间。需要注意的是,一条没有任何交易的环路的盈利效率为0。
你需要求出所有消耗时间为正数的环路中,盈利效率最高的环路的盈利效率。答案向下取整保留到整数。如果没有任何一条环路可以盈利,则输出0。

输入输出格式

输入格式:
从标准输入中读取输入数据。
第一行包含3个正整数,N、M和K,分别表示集市数量、道路数量和商品种类数量。
接下来的N行,第i行中包含2K个整数Bi,1, Si,1, Bi,2, Si,2, …, Bi,K, Si,K描述一个集市。对于任意的1≤j≤K, 整数Bi,j和Si,j分别表示在编号为i的集市上购买、卖出编号为j的商品时的交易价格。如果一个交易价格为-1,则表示这个商品在这个集市上不能进行这种交易。
接下来M行,第p行包含3个整数,Vp、Wp和Tp, 表示存在一条从编号为Vp的市场出发前往编号为Wp的市场的路径花费Tp分钟。

输出格式:
输出到标准输出中。
输出包含一个整数,表示盈利效率最高的环路盈利效率,答案向下取整保留到整数。如果没
有任何一条环路可以盈利,则输出0。

输入输出样例

输入样例#1:

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

输出样例#1:

2

说明

1≤N≤100,1≤M≤9900,1≤K≤1000。

题解

参考资料:商旅 – APIO2017-商旅题解.pdf
分数规划的模型。
考虑二分答案,对于一个二分出来的答案ans,判断是否存在环路使得效率≥ans,也就是下面的式子
\displaystyle \frac{\sum profit}{\sum time} \geq ans
转换成
\displaystyle \sum profit - ans \cdot \sum time \geq 0
考虑对任意点对(i, j)连边,权值为i买入j卖出商品的最大收益减去两点间最短路的ans倍。对这个图找是否存在正环就可以判断二分的答案是否可行。
我们需要预处理i买入j卖出商品的最大收益,枚举i和j和商品即可;预处理最短路,采用Floyd即可。预处理的总复杂度是O(N^2K+N^3)的。
每一次check,需要构建新图,Floyd判正环,考虑边权取反后判负环,就是一个最短路的常规写法。每一次check的复杂度是O(N^3)的。
因此这个算法的总复杂度是O(N^3 \log N)的。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105, MAXK = 1005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m, K;

LL gra[MAXN][MAXN], prof[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK];
LL dis[MAXN][MAXN];

inline bool check(LL mid) {
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(gra[i][j] == INF) continue;
            dis[i][j] = std::min(INF, gra[i][j] * mid - prof[i][j]);
        }
        dis[i][i] = INF;
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dis[i][j] = std::min(INF, std::min(dis[i][j], dis[i][k] + dis[k][j]));
            }
            if(dis[i][i] <= 0) return true;
        }
    }
    return false;
}

int u, v;
LL w;

int main() {
    memset(gra, 0x3f, sizeof(gra));
    n = readint(); m = readint(); K = readint();
    for(int i = 1; i <= n; i++) {
        gra[i][i] = 0;
        for(int j = 1; j <= K; j++) {
            b[i][j] = readint(); s[i][j] = readint();
        }
    }
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u][v] = std::min(gra[u][v], w);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= K; k++) {
                if(b[i][k] == -1 || s[j][k] == -1) continue;
                prof[i][j] = std::max(prof[i][j], s[j][k] - b[i][k]);
            }
        }
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                gra[i][j] = std::min(gra[i][j], gra[i][k] + gra[k][j]);
            }
        }
    }
    LL l = 0, r = 1e15, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid; else r = mid;
    }
    printf("%lld", l);
    return 0;
}
[洛谷1993]小K的农场 题解

[洛谷1993]小K的农场 题解

题目地址:洛谷:【P1993】小K的农场 – 洛谷

题目描述

小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:

  • 农场a比农场b至少多种植了c个单位的作物,
  • 农场a比农场b至多多种植了c个单位的作物,
  • 农场a与农场b种植的作物数一样多。

但是,由于小K的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

输入格式:
第一行包括两个整数 n 和 m,分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行:
如果每行的第一个数是 1,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至少多种植了 c 个单位的作物。
如果每行的第一个数是 2,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至多多种植了 c 个单位的作物。
如果每行的第一个数是 3,家下来有 2 个整数 a,b,表示农场 a 终止的数量和 b 一样多。

输出格式:
如果存在某种情况与小 K 的记忆吻合,输出“Yes”,否则输出“No”。

输入输出样例

输入样例#1:

3 3
3 1 2
1 1 3 1
2 2 3 2

输出样例#1:

Yes

说明

对于 100% 的数据保证:1 ≤ n,m,a,b,c ≤ 10000。

题解

一个差分约束的裸题。
我们考虑一组条件:
\begin{gathered} f(a) - f(b) \leq p \\ f(b) - f(c) \leq q \end{gathered}
显然有f(a) - f(c) \leq p + q。这个可以用图上的边表示出来,我们从a向b连边权p的边,b向c连边权q的边,则产生了a到c的路径,路径权值和为p+q,就能表示上面的不等式合并。
我们考虑如果a到c有多条路径,对应的是一组形如f(a) - f(c) \leq k_i的条件,我们肯定只取f(a) - f(c) \leq \min\{k_i\}即可,这在图上就是最短路。
对于本题,条件1是f(a) - f(b) \geq c转化为f(b) - f(a) \leq -c建边,条件2直接建边,条件3为f(a) - f(b) = 0,用f(a) - f(b) \leq 0f(b) - f(a) \leq 0来表示。
差分约束系统存在可行解的充要条件是图中不存在负环,即满足对于任意点,不存在f(a) - f(a) < 0的情况。我们用DFS式SPFA来判断是否存在负环。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN];

int n, m;

int dis[MAXN];
bool vis[MAXN], has;

inline void dfs(int u) {
    vis[u] = true;
    for(Edge e : gra[u]) {
        int v = e.to;
        if(dis[v] > dis[u] + e.w) {
            if(vis[v]) {
                has = true;
                return;
            }
            dis[v] = dis[u] + e.w;
            dfs(v);
        }
        if(has) return;
    }
    vis[u] = false;
}

int op, a, b, c;

int main() {
    n = readint(); m = readint();
    while(m--) {
        op = readint(); a = readint(); b = readint();
        if(op == 1) {
            c = readint();
            gra[b].push_back(Edge {a, -c});
        } else if(op == 2) {
            c = readint();
            gra[a].push_back(Edge {b, c});
        } else {
            gra[a].push_back(Edge {b, 0});
            gra[b].push_back(Edge {a, 0});
        }
    }
    for(int i = 1; i <= n; i++) {
        dfs(i);
        if(has) break;
    }
    if(has) puts("No"); else puts("Yes");
    return 0;
}