平面上有
N
N
N
N
N
N 求一个红点和蓝点的匹配，使得每个点对的曼哈顿距离之和最大，输出最小的答案。
N
≤
1000
N≤1000
N ≤ 1 0 0 0 据说奇奇怪怪限制的题，一般会想到网络流， 这题还有关点对之间的匹配，则更像是网络流。 观察题目的限制，不同的匹配权值不同，考虑使用费用流，即最大费用最大流。 由于曼哈顿距离的式子中有绝对值，先把绝对值拆开，会出现四种情况，分别是
(
x
i
−
x
j
)
+
(
y
i
−
y
j
)
(x_i-x_j)+(y_i-y_j)
( x i − x j ) + ( y i − y j )
(
x
i
−
x
j
)
+
(
y
j
−
y
i
)
(x_i-x_j)+(y_j-y_i)
( x i − x j ) + ( y j − y i )
(
x
j
−
x
i
)
+
(
y
i
−
y
j
)
(x_j-x_i)+(y_i-y_j)
( x j − x i ) + ( y i − y j )
(
x
j
−
x
i
)
+
(
y
j
−
y
i
)
(x_j-x_i)+(y_j-y_i)
( x j − x i ) + ( y j − y i )
先从源点连向每个红点的位置（简称为红点），费用为
0
0
0 接着上述四种情况对应另外新设的四个点，每个红点往这四个点连边，容量正无穷，费用为这个点的代表的式子中
x
i
x_i
x i
x
j
x_j
x j 但是会发现，这样能保证流出的费用正好是曼哈顿距离吗？如果一对匹配不是恰好在大减小的位置流过，那不就错了吗？ 其实会发现，因为题目求的是最大费用，而加上绝对值一定是大于等于没有绝对值的，所以最终流过去的方案必然会是曼哈顿距离，且必为最优解。 至于最大费用最大流，只需要把费用流SPFA中的最短路改成最长路即可。 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define ll long long
int last[ N* 2 ] , cur[ N* 2 ] , len= 1 ;
ll dis[ N* 2 ] ;
int q[ N* 2 ] , p[ N* 2 ] ;
ll ans= 0 ;
struct
{
int c, w, to, next;
} a[ N* 20 ] ;
int n, ns, m;
void add ( int x, int y, int c, int w)
{
a[ ++ len] . to= y;
a[ len] . next= last[ x] ;
a[ len] . c= c, a[ len] . w= w;
last[ x] = len;
}
int id = 0 ;
int SPFA ( )
{
for ( int i= 0 ; i<= ns; i++ ) dis[ i] = - 1e16 ;
q[ 1 ] = 0 , p[ 0 ] = ++ id, dis[ 0 ] = 0 ;
int l= 0 , r= 1 ;
while ( l!= r)
{
l= l% ( ns+ 10 ) + 1 ;
int k= q[ l] ;
p[ k] = 0 ;
for ( int i= last[ k] ; i; i= a[ i] . next)
{
int x= a[ i] . to;
if ( dis[ k] + a[ i] . w> dis[ x] && a[ i] . c)
{
dis[ x] = dis[ k] + a[ i] . w;
if ( p[ x] < id)
{
p[ x] = id;
r= r% ( ns+ 10 ) + 1 ;
q[ r] = x;
}
}
}
}
return dis[ ns] > 0 ;
}
int dfs ( int k, int flow)
{
if ( k== ns) return flow;
int have= 0 ;
p[ k] = 1 ;
for ( int i= cur[ k] ; i; i= a[ i] . next)
{
int x= a[ i] . to;
if ( ! p[ x] && dis[ k] + a[ i] . w== dis[ x] && a[ i] . c)
{
cur[ k] = i;
int t= min ( flow- have, a[ i] . c) ;
int now= dfs ( x, t) ;
ans+ = ( ll) now* a[ i] . w;
have+ = now, a[ i] . c- = now, a[ i^ 1 ] . c+ = now;
if ( have== flow) break ;
}
}
p[ k] = 0 ;
return have;
}
int main ( )
{
int i, x, y, c;
scanf ( "%d" , & n) ;
for ( i= 1 ; i<= n; i++ )
{
scanf ( "%d%d%d" , & x, & y, & c) ;
add ( i, 2 * n+ 1 , c, x+ y) ;
add ( 2 * n+ 1 , i, 0 , - x- y) ;
add ( i, 2 * n+ 2 , c, x- y) ;
add ( 2 * n+ 2 , i, 0 , y- x) ;
add ( i, 2 * n+ 3 , c, y- x) ;
add ( 2 * n+ 3 , i, 0 , x- y) ;
add ( i, 2 * n+ 4 , c, - x- y) ;
add ( 2 * n+ 4 , i, 0 , x+ y) ;
add ( 0 , i, c, 0 ) ;
add ( i, 0 , 0 , 0 ) ;
}
for ( i= 1 ; i<= n; i++ )
{
scanf ( "%d%d%d" , & x, & y, & c) ;
add ( 2 * n+ 1 , i+ n, 1e6 , - x- y) ;
add ( i+ n, 2 * n+ 1 , 0 , x+ y) ;
add ( 2 * n+ 2 , i+ n, 1e6 , y- x) ;
add ( i+ n, 2 * n+ 2 , 0 , x- y) ;
add ( 2 * n+ 3 , i+ n, 1e6 , x- y) ;
add ( i+ n, 2 * n+ 3 , 0 , y- x) ;
add ( 2 * n+ 4 , i+ n, 1e6 , x+ y) ;
add ( i+ n, 2 * n+ 4 , 0 , - x- y) ;
add ( i+ n, 2 * n+ 5 , c, 0 ) ;
add ( 2 * n+ 5 , i+ n, 0 , 0 ) ;
}
ns= 2 * n+ 5 ;
while ( SPFA ( ) )
{
while ( 1 ) {
for ( i = 0 ; i <= ns; i++ ) cur[ i] = last[ i] ;
int t = dfs ( 0 , 1e6 ) ;
if ( ! t) break ;
}
}
printf ( "%lld" , ans) ;
return 0 ;
}