BZOJ3597 [Scoi2014]方伯伯运椰子 【二分 + 判负环】

题目链接

BZOJ3597

题解

orz一眼过去一点思路都没有

既然是流量网络，就要借鉴网络流的思想了

我们先处理一下那个比值，显然是一个分数规划，我们二分一个\(\lambda = \frac{X - Y}{k}\)
如果\(\lambda\)成立，则
\[\lambda \le \frac{X - Y}{k}\]
即
\[\lambda k + (Y - X) \le 0\]
所以我们只需要判断是否存在一种方案使得这个式子成立

依照网络流的思想，撤回流量就往反向边走，扩展流量往正向边
对于边\((u,v)\)，撤回流量产生的代价就是\(\lambda + \Delta fee = \lambda + (ai - di)\)
扩展产生的代价就是\(\lambda + \Delta fee = \lambda + (bi + di)\)
为保证流量守恒，我们调整边走过的路径必须成环
如果我们建出的图中存在权值为负的环，就找到了一条满足上式的调整方案
使用\(spfa\)判负环即可

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,0,sizeof(s)) #define cp pair<int,int> #define LL long long int #define eps 1e-4 using namespace std; const int maxn = 5005,maxm = 10005,INF = 1000000000; inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag; } int h[maxn],ne; struct EDGE{int to,nxt; double w;}ed[maxm]; inline void build(int u,int v,double w){ed[++ne] = (EDGE){v,h[u],w}; h[u] = ne; } int n,m,vis[maxn]; double d[maxn]; bool spfa(int u,double lam){vis[u] = true;Redge(u){to = ed[k].to;if (d[to] > d[u] + ed[k].w + lam){d[to] = d[u] + ed[k].w + lam;if (vis[to]) return true;if (spfa(to,lam)) return true;}}vis[u] = false;return false; } bool check(double lam){cls(vis); cls(d);for (int i = 1; i <= n; i++) if (spfa(i,lam)) return true;return false; } int main(){n = read() + 2; m = read();int u,v,a,b,c,d;for (int i = 1; i <= m; i++){u = read(); v = read(); a = read(); b = read(); c = read(); d = read();if (u == n - 1 || v == n - 1) continue;if (c) build(v,u,a - d);build(u,v,d + b);}double l = 0,r = 1000000000,mid;while (r - l > eps){mid = (l + r) / 2.0;if (check(mid)) l = mid;else r = mid;}printf("%.2lf",(l + r) / 2.0);return 0; }

转载于:https://www.cnblogs.com/Mychael/p/9037002.html

新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的BZOJ3597 [Scoi2014]方伯伯运椰子 【二分 + 判负环】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。