题解
目标就是
\[Maximize\ \lambda = \frac{X-Y}{k}
\]
\]
按照分数规划的一般规律,
构造:
\[g(\lambda) = \lambda k + Y - X
\]
\]
由于总流量不变,我们考虑转移流量。
注意到,对于每条边,我们如果增加其容量则会增加(b[i]+d[i]+lambda)点值,如果减少就是(a[i]-d[i]+lambda)点值。
如果可以构成一个负环,那么就一定可以更优。
所以我们二分\(\lambda\),check即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-5
struct haha {
int x, y, a, b, c, d;
};
struct edge {
int from, to;
double cost;
};
const int maxn = 5005;
vector<edge> G[maxn];
haha b[maxn];
int n, m;
int vis[maxn], flag;
double dist[maxn];
void add_edge(int from, int to, double cost) {
G[from].push_back((edge){from, to, cost});
}
void dfs(int i) {
vis[i] = 1;
for (int j = 0; j < G[i].size(); j++) {
edge &e = G[i][j];
if (dist[e.to] > dist[i] + e.cost) {
if (vis[e.to])
flag = 1;
else {
dist[e.to] = dist[i] + e.cost;
dfs(e.to);
}
}
}
vis[i] = 0;
}
bool check(double lambda) {
for (int i = 1; i <= n; i++)
G[i].clear();
for (int i = 1; i <= m; i++) {
if (b[i].c)
add_edge(b[i].y, b[i].x, b[i].a - b[i].d + lambda);
add_edge(b[i].x, b[i].y, b[i].b + b[i].d + lambda);
}
flag = 0;
memset(vis, 0, sizeof(vis));
memset(dist, 0, sizeof(dist));
for (int i = 1; i <= n && !flag; i++) {
dfs(i);
}
return flag;
}
int main() {
// freopen("input", "r", stdin);
scanf("%d %d", &n, &m);
n += 2;
for (int i = 1; i <= m; i++)
scanf("%d%d%d%d%d%d", &b[i].x, &b[i].y, &b[i].a, &b[i].b, &b[i].c, &b[i].d);
double L = 0, R = 10000000;
while (R - L > eps) {
double mid = (L + R) / 2;
if (check(mid))
L = mid;
else
R = mid;
}
printf("%.2f\n", L);
}
总结
- 图上的分数规划问题要考虑分摊到每个边上。
- 分数规划问题要注意double的赋值。