AtCoder Beginner Contest 324（F）

AtCoder Beginner Contest 324

F Beautiful Path

需要一点思维的转化，一时竟然没想到。

题意

给定大小为 $n$ 的有向图，$m$ 条边，每条边有 $b_i,c_i$ 两个属性，需要找到一条从 $1\sim n$ 的路径使得 $w_i=(b_1+b_2+\cdots +b_k)/(c_1+c_2+\cdots +c_k)$ 最大。题目保证路径一定存在且无环。

思路

初看一时没思路，写了个到达 $u$ 点时，以 $w_i$ 的最大值为最优跑拓扑排序，这样显然是不对的，例如：$\frac{1}{1}\to \frac{3}{2}=\frac{1+3}{1+2}$ 会比 $\frac{1}{1}\to \frac{1}{1}=\frac{1+1}{1+1}$ 更优，但是若是下一条边是 $\frac{100}{1}$，两条路径更优的是 $\frac{1+1+100}{1+1+1}>\frac{1+3+100}{1+2+1}$.

这里需要转换一下思路：
求路径使得 $\max (b_1+b_2+b_3)/(c_1+c_2+c_3)=w_i$
设答案为 $res$
$(b_1+b_2+b_3)/(c_1+c_2+c_3)=res$
$(b_1+b_2+b_3)=(c_1+c_2+c_3)\ast res$
$b_1-c_1\ast res+b_2-c_2\ast res+b_3-c_3\ast res=0$
上式将 $=$ 改成 $\ge$ 显然也成立，于是就有了单调性，二分答案求解。

用拓扑排序时有个小坑点，从 $1$ 出发可能有些节点到达不了，需要清除这些点的度。或者由于一定是小编号 $\to$ 大编号，可以直接循环求解。

代码

#include <bits/stdc++.h>
using namespace std;#define ll long long
#define double long doubleconst int N = 2e5 + 10;struct node{int v, b, c;
};
vector<node> g[N];int n, m, d[N], t[N];
double f[N];
bool topu(double x){queue<int> q;for(int i = 1; i <= n; i ++){t[i] = d[i];f[i] = -1e10;}q.push(1);f[1] = 0.0;while(!q.empty()){int u = q.front(); q.pop();for(auto [v, b, c] : g[u]){f[v] = max(f[v], f[u] + (double)b - (double)c * x);t[v] --;if(!t[v]) q.push(v);}}return f[n] >= 0;
}int vis[N];
void dfs(int u){if(vis[u]) return ;vis[u] = 1;for(auto [v, a, b] : g[u]) dfs(v);
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i ++){int u, v, b, c;cin >> u >> v >> b >> c;g[u].push_back({v, b, c});d[v] ++;}dfs(1);for(int i = 1; i <= n; i ++){ // 清除无法到达的节点的度if(vis[i]) continue ;for(auto [v, a, b] : g[i]) d[v] --;}double l = 0, r = 2e9;for(int i = 1; i <= 100; i ++){double mid = (l + r) / 2;if(topu(mid)) l = mid;else r = mid;}cout << fixed << setprecision(20) << l <<"\n";return 0;
}

G Generate Arrays（待补）

题意

思路

代码