[洛谷1901]发射站 题解
题目地址:洛谷:【P1901】发射站 – 洛谷 题目描述 某地有 N 个能量发 …
May all the beauty be blessed.
题目地址:洛谷:【P2939】[USACO09FEB]改造路Revamping Trails – 洛谷、BZOJ:Problem 1579. — [Usaco2009 Feb]Revamping Trails 道路升级
Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John’s farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.
He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail’s traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.
约翰一共有N个牧场.由M条布满尘埃的小径连接.小径可以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.
通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径,使之成为高速公路.在高速公路上的通行几乎是瞬间完成的,所以高速公路的通行时间为0.
请帮助约翰决定对哪些小径进行升级,使他每天早上到牧场W花的时间最少.输出这个最少的时间.
输入格式:
* Line 1: Three space-separated integers: N, M, and K
* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1_i, P2_i, and T_i
输出格式:
* Line 1: The length of the shortest path after revamping no more than K edges
输入样例#1:
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100
输出样例#1:
1
K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 1.
考虑分层图最短路。令dis[i][j]为在第i个点且已经建了j条高速公路的最短路距离,最短路转移的时候向相邻点同层转移,加权为边权;向相邻点下一层转移,无加权,表示该边修了一条高速公路。修满k条比不修满k条肯定更优,因此答案为dis[n][k]。
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>
#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 = 10005;
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
int n, m, k;
int dis[MAXN][25];
bool vis[MAXN][25];
struct Node {
int u, k, w;
inline bool operator<(const Node &rhs) const {
return w > rhs.w;
}
};
std::priority_queue<Node> pq;
inline void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
pq.push(Node {1, 0, 0});
dis[1][0] = 0;
while(!pq.empty()) {
Node t = pq.top(); pq.pop();
if(vis[t.u][t.k]) continue;
vis[t.u][t.k] = true;
for(auto e : gra[t.u]) {
if(dis[e.to][t.k] > dis[t.u][t.k] + e.w) {
dis[e.to][t.k] = dis[t.u][t.k] + e.w;
pq.push(Node {e.to, t.k, dis[e.to][t.k]});
}
if(t.k < k && dis[e.to][t.k + 1] > dis[t.u][t.k]) {
dis[e.to][t.k + 1] = dis[t.u][t.k];
pq.push(Node {e.to, t.k + 1, dis[e.to][t.k + 1]});
}
}
}
}
int u, v, w;
int main() {
n = readint(); m = readint(); k = readint();
for(int i = 1; i <= m; i++) {
u = readint(); v = readint(); w = readint();
gra[u].push_back(Edge {v, w});
gra[v].push_back(Edge {u, w});
}
dijkstra();
printf("%d", dis[n][k]);
return 0;
}
题目地址:洛谷:【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;
}
题目地址:洛谷:【P2341】[HAOI2006]受欢迎的牛 – 洛谷、BZOJ:Problem 1051. — [HAOI2006]受欢迎的牛
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。
输入格式:
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B
输出格式:
第一行:单独一个整数,表示明星奶牛的数量
输入样例#1:
3 3 1 2 2 1 2 3
输出样例#1:
1
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
Tarjan缩点练手。
同一SCC内的所有点都可以互达,因此不用考虑SCC内的情况,直接缩点解决。考虑出度问题,只有当一个点作为一棵叶子到根的有向树的树根时才有答案,因此有多棵树的情况是无解的。考虑出度,如果出度为0的点有两个则答案为0,如果只有一个该SCC的大小就是答案。
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <utility>
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;
int n, m;
std::vector<int> gra[MAXN], gran[MAXN];
int deg[MAXN];
int dfn[MAXN], low[MAXN], sno[MAXN], clk, scc;
std::stack<int> sta;
bool insta[MAXN];
inline void tarjan(int u) {
dfn[u] = low[u] = ++clk;
insta[u] = true; sta.push(u);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(!dfn[v]) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if(insta[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
scc++;
int p;
do {
p = sta.top(); sta.pop();
insta[p] = false;
sno[p] = scc;
} while(p != u);
}
}
std::set<std::pair<int, int> > edges;
int u, v;
int main() {
n = readint(); m = readint();
for(int i = 1; i <= m; i++) {
u = readint(); v = readint();
gra[u].push_back(v);
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}
for(int u = 1; u <= n; u++) {
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(sno[u] != sno[v] && !edges.count(std::pair<int, int>(sno[u], sno[v]))) {
edges.insert(std::pair<int, int>(sno[u], sno[v]));
gran[sno[u]].push_back(sno[v]);
deg[sno[u]]++;
}
}
}
int ansn = -1;
for(int i = 1; i <= scc; i++) {
if(!deg[i] && ansn != -1) {
puts("0");
return 0;
}
if(!deg[i] && ansn == -1) {
ansn = i;
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(sno[i] == ansn) {
ans++;
}
}
printf("%d", ans);
return 0;
}