Description
DZY 家的后院有一块地, 由 \(n\) 行 \(m\) 列的方格组成, 格子内种的菜有一定的价值, 并且每一条单位长度的格线有一定的费用.
DZY 喜欢在地里散步. 他总是从任意一个格点出发, 沿着格线行走直到回到出发点, 且在行走途中不允许与已走过的路线有任何相交或触碰 (出发点除外). 记这条封闭路线内部的格子总价值为 \(V\), 路线上的费用总和为 \(C\), DZY 想知道 \(\frac{V}{C}\) 的最大值是多少.
Input
第一行为两个正整数 \(n, m\).
接下来 \(n\) 行, 每行 \(m\) 个非负整数, 表示对应格子的价值.
接下来 \(n+1\) 行, 每行 \(m\) 个正整数, 表示所有横向的格线上的费用.
接下来 \(n\) 行, 每行 \(m+1\) 个正整数, 表示所有纵向的格线上的费用.
Output
输出一行仅含一个数, 表示最大的 \(\frac{V}{C}\), 保留 \(3\) 位小数.
Sample Input
3 4
1 3 3 3
1 3 1 1
3 3 1 0
100 1 1 1
97 96 1 1
1 93 92 92
1 1 90 90
98 1 99 99 1
95 1 1 1 94
1 91 1 1 89Sample Output
1.286Data Range
对于 100% 的数据,\(n, m \leq 50, 0 \leq V_i \leq 100, 1 \leq C_i \leq 100\).
Explanation
相当于需要选取一堆连通的格子, 费用总和为被选中的方格和外部方格的割.
然后因为你打算求一个结果而不是如何得到结果对吧...... 所以应该是一个二分答案然后再用最小割判定 (我也不知道应该怎么解释怎么想到的)
最小割的意思就是说用这个代价有没有可能把需要的图形割出来.
任何一个方格被选中都应该考虑其四边的权重之和为这个方格被选中的代价; 同时选择两个格子即会抵消掉这个价值 (也就是连了一条边).
然后为什么这个二分答案是单调的呢~ 因为其实我们可以这样理解这件事: 如果真的选了两个块出来, 那么有两种情况. 第一种是两个比值 \(\frac{V}{C}\) 相同, 则对结果无影响; 第二种是一个大一个小, 那么选择小的那个一定更好. 所以综合来讲选了一个一定能选一个更好一点的 (或者一样好).
就是一个二分答案加最小割判定.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 5010, maxm = 800100, maxN = 64;
const int infinit = 0x3fffffff;
const llf epsilon = 1e-6;
class Dinic
{
public:
struct edge
{
int u, v; llf flow;
edge *next, *rev;
};
int n, s, t, ecnt;
edge *edges[maxn], epool[maxm];
int level[maxn];
void add_edge(int u, int v, llf flow, llf revflow=0.0)
{
// printf("add edge %d %d %.3lf\n", u, v, flow);
// printf("add edge %d %d %.3lf\n", v, u, revflow);
edge *p = &epool[++ecnt],
*q = &epool[++ecnt];
p->u = u; p->v = v; p->flow = flow;
p->next = edges[u]; edges[u] = p, p->rev = q;
q->u = v; q->v = u; q->flow = revflow;
q->next = edges[v]; edges[v] = q, q->rev = p;
return ;
}
bool make_level(void)
{
memset(level, 0, sizeof(level));
queue<int> que;
que.push(s);
level[s] = 1;
while (!que.empty()) {
int p = que.front();
que.pop();
for (edge *ep = edges[p]; ep; ep = ep->next)
if (ep->flow > 0 && !level[ep->v]) {
level[ep->v] = level[p] + 1;
que.push(ep->v);
}
}
if (level[t] > 0)
return true;
return false;
}
llf find(int p, llf mn)
{
if (p == t)
return mn;
llf tmp = 0, sum = 0;
for (edge *ep = edges[p]; ep && sum < mn - epsilon; ep = ep->next)
if (level[ep->v] == level[p] + 1 && ep->flow) {
tmp = find(ep->v, min(mn - sum, ep->flow));
if (tmp > epsilon) {
sum += tmp;
ep->flow -= tmp;
ep->rev->flow += tmp;
}
}
if (fabs(sum) <= epsilon)
level[p] = 0;
return sum;
}
void clear(void)
{
memset(edges, 0, sizeof(edges));
ecnt = 0;
return ;
}
llf eval(void)
{
llf sum = 0;
while (make_level())
sum += find(s, infinit);
return sum;
}
} graph;
int n, m;
int id[maxN][maxN], a[maxN][maxN], b[maxN][maxN], c[maxN][maxN];
void build_graph(llf x)
{
graph.clear();
rep(i, 1, n) rep(j, 1, m) {
graph.add_edge(graph.s, id[i][j], a[i][j]);
} rep(i, 1, n) rep(j, 1, m) {
int tmp = 0;
if (i == 1) tmp += b[i][j];
if (i == n) tmp += b[i+1][j];
if (j == 1) tmp += c[i][j];
if (j == m) tmp += c[i][j+1];
graph.add_edge(id[i][j], graph.t, tmp * x);
} rep(i, 1, n - 1) rep(j, 1, m) {
graph.add_edge(id[i][j], id[i+1][j], b[i+1][j] * x, b[i+1][j] * x);
} rep(i, 1, n) rep(j, 1, m - 1) {
graph.add_edge(id[i][j], id[i][j+1], c[i][j+1] * x, c[i][j+1] * x);
}
return ;
}
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
rep(i, 0, n) rep(j, 0, m) { int tmp = (i-1)*m+j;
if (tmp < 1 || tmp > n * m) tmp = n * m;
id[i][j] = tmp; }
int sum = 0;
rep(i, 1, n) rep(j, 1, m)
scanf("%d", &a[i][j]), sum += a[i][j];
rep(i, 1, n + 1) rep(j, 1, m)
scanf("%d", &b[i][j]);
rep(i, 1, n) rep(j, 1, m + 1)
scanf("%d", &c[i][j]);
// Defining properties
graph.n = n * m + 2;
graph.s = 0;
graph.t = graph.n - 1;
// Binary searching
llf l = 0, r = 1000000;
while (fabs(r - l) > epsilon) {
llf mid = (l + r) / 2;
build_graph(mid);
llf work = graph.eval();
if (sum - work > epsilon)
l = mid;
else
r = mid;
}
// Output
printf("%.3lf\n", l);
return 0;
}