【分数规划】[Scoi2014] bzoj3597方伯伯运椰子

【分数规划】[Scoi2014] bzoj3597方伯伯运椰子

题目点这里

orz看到accept好开心 感觉自己写了快一上午的分数规划没白费………………

在我去年去省选时候看到这道题根本不知道他在干啥

（后面的就更不知道了）

后来学了网络流以为这题是网络流_(:з)∠)_

可是它竟然是0/1分数规划！！

其实知道算法了看角虫们的题解窝还是看不懂……一堆公式推起来好高端 = =

于是就顺着他们的思路自己YY了。。然后竟然就对了…………

我的思路是这样的：

原来有一个流了而且还是满流 然后要求我们不能改变总流量而且每条边也都必须是满流

所以我们不能生产流量！只能做流量的搬运工…………

那么我们建图就可以把每条边的边权设为把每流量从u搬运到v需要花多少钱

则对于提上给出来的 u 和 v 建一条u 到 v 权值为 b + d 的边和一条 v 到 u 权值为 a - d的边（当c == 0 时 不建 v 到 u 的边）

于是图上的每个环就是一种搬运的方案 并且因为求的是平均价值 所以每种方案的价值与到底搬运多少无关

假设最优解为ans 于是对于图上的每个环 都有 ans * n + sigma(w) >= 0 （n为环上点的个数 w为环上的边的权值）

 二分答案。当 mid < ans 时 一定存在一个环使得 mid * n + sigma(w) < 0 即存在负环 当 mid >= ans 时不存在负环

（对于式中 mid * n 的处理很简单 因为w的数量和n是相等的 所以把所有边权加上mid就可以了）

有一个细节是N读入以后要记得+2 之前没加就WA了…………

判断负环写spfa就行了 窝不会高端的dfs版spfa……听说dfs版的判断负环特别快 = = 你非要卡我bfs的话我也没办法啊。。

#include <cstdio>
#include <iostream>
#include <queue>#define eps 1e-4using namespace std;int read()
{int sign = 1, n = 0; char c = getchar();while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }return sign*n;
}const int Nmax = 505;
const int Mmax = 3003;int N, M; 
struct ed{int v, next;double w;
}e[Mmax * 2];
int k = 1, head[Nmax];inline void adde(int u, int v, int w)
{e[k] = (ed){ v, head[u], w };head[u] = k++;
}queue <int> q;
bool vis[Nmax]; 
double dis[Nmax];
int cnt[Nmax];bool spfa(double &mid)
{while(q.size()) q.pop();for(int i = 1; i <= N; ++i){dis[i] = cnt[i] = 0;vis[i] = 1; q.push(i);} while(q.size()){int u = q.front(); q.pop(); vis[u] = 0;for(int i = head[u]; i; i = e[i].next){int v = e[i].v;if(dis[u] + mid + e[i].w < dis[v]){dis[v] = dis[u] + mid + e[i].w;if(++cnt[v] >= N) return 1;if(!vis[v]) { vis[v] = 1; q.push(v); } }}}return 0;
}int main()
{N = read() + 2; M = read();while(M--){int u = read(), v = read(), a = read(), b = read(), c = read(), d = read();adde(u, v, b + d);if(c) adde(v, u, a - d);}double l = 0.0, r = 1e10;while(r - l > eps){double mid = (l + r) * 0.5;if(spfa(mid)) l = mid;else r = mid;}printf("%.2fn", l + eps);return 0;
}

好吧 我来贴dfs版的spfa了

#include <cstdio>
#include <iostream>
#include <queue>using namespace std;int read()
{int sign = 1, n = 0; char c = getchar();while(c < '0' || c > '9') { if(c == '-')sign = -1; c = getchar(); }while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }return sign * n;
}const double inf = 1e4;
const double eps = 1e-4;
const int Nmax = 505;
const int Mmax = 3005;int N, M;
struct ed{int v, next;double w;
}e[Mmax * 2];
int k = 1, head[Nmax];inline void adde(int u, int v, int w)
{//printf("%d → %d : %dn", u, v, w);e[k] = (ed){ v, head[u], (double)w }; head[u] = k++;
}double dis[Nmax];
bool vis[Nmax];bool spfa(int u, double &mid)
{vis[u] = true;for(int i = head[u]; i; i = e[i].next){int v = e[i].v;if(dis[v] > dis[u] + mid + e[i].w){dis[v] = dis[u] + mid + e[i].w;if(vis[v] || spfa(v, mid)) return true;}}return vis[u] = false;
} inline bool check(double mid) 
{for(int i = 1; i <= N; ++i) dis[i] = vis[i] = 0;for(int i = 1; i <= N; ++i) if(spfa(i, mid)) return true;return false;
}int main()
{freopen("coconut.in", "r", stdin);freopen("coconut.out", "w", stdout);N = read() + 2; M = read();for(int i = 1; i <= M; ++i){int u = read(), v = read(), a = read(), b = read(), c = read(), d = read();adde(u, v, b + d);if(c) adde(v, u, a - d);}double L = 0.0, R = inf, mid;while(R - L > eps){mid = (L + R) * 0.5;if(check(mid)) L = mid;else R = mid;}printf("%.2lfn", L + eps);return 0;
}