Address
Solution
- 将 \(c_i\) 看作边 \((u_i,v_i)\) 的流量，并将每条边的容量都看作 \(∞\)。
- 将 \(a_i\) 看作把边 \((u_i,v_i)\) 增广 \(1\) 单位流量的花费，\(b_i\) 看作将 \((u_i,v_i)\) 退 \(1\) 单位流量的花费，也就是把边 \((v_i,u_i)\) 增广 \(1\) 单位流量的花费。
- 将 \(d_i\) 看作把边 \((u_i,v_i)\) 增广 \(1\) 单位流量的代价，同时也看作把边 \((v_i,u_i)\) 增广 \(1\) 单位流量的收益。
- 令 \(res=X-Y\)，显然 \(\lfloor\) 把 \((u_i,v_i)\) 增广 \(1\) 单位流量 \(\rfloor\) 对 \(res\) 的贡献是 \(-b_i-d_i\)， \(\lfloor\) 把 \((v_i,u_i)\) 增广 \(1\) 单位流量 \(\rfloor\) 对 \(res\) 的贡献是 \(d_i-a_i\)。
- 注意 \(c_i=0\) 时，不能增广 \((v_i,u_i)\)。
- 先按上面所说的建好一张新图。
- 题目要求流量不能变少，又因为流量变多肯定不优，所以我们要让流量不变。
- 也就是说我们要增广一些环。
- 看到 \((X-Y)/k\)，显然的分数规划模型。
- 二分答案，判断是否 \(res/k≥mid\)，即是否 \(res-mid*k≥0\)。
- 考虑将新图上的每条边减去 \(mid\)，然后如果图上存在一个环使得边权和非负，那么 \(res/k≥mid\)。
Code
#include <bits/stdc++.h>
using namespace std;
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = 1e5 + 5;
const double inf = 1e18, eps = 1e-4;
int n, m, adj[e], nxt[e], go[e], num, s, cnt[e];
double len[e], ans, dis[e];
bool vis[e];
inline void add(int x, int y, double v)
{
nxt[++num] = adj[x]; adj[x] = num; go[num] = y; len[num] = v;
}
inline bool check(double mid)
{
queue<int>q;
int i;
for (i = 1; i <= n + 2; i++) vis[i] = 1, dis[i] = 0, cnt[i] = 1, q.push(i);
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (i = adj[u]; i; i = nxt[i])
{
int v = go[i];
if (dis[u] + len[i] - mid >= dis[v])
{
dis[v] = dis[u] + len[i] - mid;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n + 2) return 1;
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return 0;
}
int main()
{
int i, u, v, ai, bi, ci, di;
read(n); read(m); m--;
while (m--)
{
read(u); read(v); read(ai); read(bi); read(ci); read(di);
add(u, v, -bi - di);
if (ci) add(v, u, di - ai);
}
read(u); read(s); read(ai); read(bi); read(ci); read(di);
double l = 0, r = 1e9;
while (r - l > eps)
{
double mid = (l + r) / 2.0;
if (check(mid)) ans = l = mid;
else r = mid;
}
printf("%.2lf\n", ans);
return 0;
}