(mathcal{Description})
Link.
给定一个 (n imes n) 的格点图，横纵相邻的两格点有一条边权为二元组 ((w,e)) 的边。求对于 (S=(1,1)) 和 (T=(n,n)) 的一个割，使得 ((sum w)(sum c)) 最小。
(nle400)。
(mathcal{Solution})
套路题，P5540 + P4001。所以我把这两题题解合二为一。
假设边权都是普通的数字，考虑怎么快速求出这个格点图的最小割。可以发现，这个图一定是一个平面图，那么把它形象化为图形，脑补一下得出一个割肯定是一条完整的曲线，从图的左下方贯穿到图的右上方。所以建立左下方和右上方的超级源汇，每条边相当于连接其左右两个面，最后求源汇之间的最短路即为原图最小割。
回到本题，对于任意一个割，设其 (sum w=w_0)，(sum e=e_0)，将它体现为一个坐标 ((w_0,e_0))，问题就转化为：(mathbb R^2) 的一象限有若干个点，求出其中 (xy) 最小的点。
记 (A(x_1,y_1)) 为这些点中 (x) 最小的，(B(x_2,y_2)) 为 (y) 最小的（都能直接求出），考虑在 (AB) 的下方取出一个特殊的点 (C(x_3,y_3))，最大化 (S_{ riangle ABC})。推一下式子：
[egin{aligned}
S_{ riangle ABC}&=frac{-vec{AB} imes vec{AC}}{2}\
&=-frac{1}{2}[(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)]\
&=-frac{1}2[(y_1-y_2)x_3+(x_2-x_1)y_3-x_2y_1+x_1y_2]
end{aligned}
]
把 ((y_1-y_2)w+(x_2-x_1)e) 作为边 ((w,e)) 的权，跑最小割即得 (C)。用 (C) 更新答案最后，分治处理 ((A,C)) 和 ((C,B)) 直到 (C) 不存在终止，答案就求到啦。
(mathcal{Code})
/* Clearink */
#include <queue>
#include <cstdio>
#include <assert.h>
typedef long long LL;
inline int rint () {
int x = 0, f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x * f;
}
inline void chkmin ( LL& a, const LL b ) { b < a && ( a = b, 0 ); }
const int MAXN = 400, INF = 0x3f3f3f3f;
int n, S, T;
LL coeW, coeE, ans = 1ll << 60;
struct Value {
LL w, e;
Value ( const LL v = 0 ): w ( v ), e ( v ) {}
Value ( const LL a, const LL b ): w ( a ), e ( b ) {}
inline operator LL () const { return w + e; }
inline LL operator * ( const Value& v ) const { return w * v.e - e * v.w; }
inline Value operator + ( const Value& v ) const { return { w + v.w, e + v.e }; }
inline Value operator - ( const Value& v ) const { return { w - v.w, e - v.e }; }
inline bool operator < ( const Value& v ) const {
return coeW * w + coeE * e < coeW * v.w + coeE * v.e;
}
};
typedef std::pair<Value, int> PVI;
struct Graph {
static const int MAXND = MAXN * MAXN + 2, MAXEG = 4 * MAXN * ( MAXN + 1 );
int bound, ecnt, head[MAXND + 5], to[MAXEG + 5], nxt[MAXEG + 5];
Value cst[MAXEG + 5], dist[MAXND + 5];
inline void operator () ( const int s, const int t, const Value& c ) {
#ifdef RYBY
printf ( "%d %d (%lld,%lld)
", s, t, c.w, c.e );
#endif
to[++ecnt] = t, cst[ecnt] = c, nxt[ecnt] = head[s];
head[s] = ecnt;
to[++ecnt] = s, cst[ecnt] = c, nxt[ecnt] = head[t];
head[t] = ecnt;
}
inline Value dijkstra ( const int s, const int t ) {
static bool vis[MAXND + 5];
static std::priority_queue<PVI, std::vector<PVI>, std::greater<PVI> > heap;
for ( int i = 1; i <= bound; ++i ) vis[i] = false, dist[i] = INF;
heap.push ( { dist[s] = 0, s } );
while ( !heap.empty () ) {
PVI p ( heap.top () ); heap.pop ();
if ( vis[p.second] ) continue;
vis[p.second] = true;
for ( int i = head[p.second], v; i; i = nxt[i] ) {
if ( Value d ( p.first + cst[i] ); d < dist[v = to[i]] ) {
heap.push ( { dist[v] = d, v } );
}
}
}
return dist[t];
}
} graph;
inline int id ( const int i, const int j ) {
if ( !i || j == n ) return S;
if ( i == n || !j ) return T;
return ( i - 1 ) * ( n - 1 ) + j;
}
inline Value calc ( const LL a, const LL b ) {
coeW = a, coeE = b;
Value ret ( graph.dijkstra ( S, T ) );
#ifdef RYBY
printf ( "calc(%lld,%lld) = (%lld,%lld)
", a, b, ret.w, ret.e );
#endif
return graph.dijkstra ( S, T );
}
inline void solve ( const Value& A, const Value& B ) {
LL a = A.e - B.e, b = B.w - A.w;
Value C ( calc ( a, b ) );
chkmin ( ans, C.w * C.e );
#ifdef RYBY
printf ( "(%lld,%lld), (%lld,%lld), (%lld,%lld)
", A.w, A.e, C.w, C.e, B.w, B.e );
printf ( "%lld...%lld
", ( B - A ) * ( C - A ), a * C.w + b * C.e + A.w * B.e - A.e * B.w );
#endif
if ( ( B - A ) * ( C - A ) >= 0 ) return ;
solve ( A, C ), solve ( C, B );
}
int main () {
n = rint ();
S = ( n - 1 ) * ( n - 1 ) + 1, T = S + 1;
graph.bound = ( n - 1 ) * ( n - 1 ) + 2;
for ( int i = 1; i < n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
int cw = rint (), ce = rint ();
graph ( id ( i, j - 1 ), id ( i, j ), { cw, ce } );
}
}
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j < n; ++j ) {
int rw = rint (), re = rint ();
graph ( id ( i - 1, j ), id ( i, j ), { rw, re } );
}
}
Value A ( calc ( 1, 0 ) ), B ( calc ( 0, 1 ) );
chkmin ( ans, A.w * A.e ), chkmin ( ans, B.w * B.e );
solve ( A, B );
printf ( "%lld
", ans );
return 0;
}
(mathcal{Details})
虽然套路但毕竟是黑的，一眼秒掉好开心 owo。