Problem Statement
Snuke is playing with red and blue balls, placing them on a two-dimensional plane.
First, he performed $N$ operations to place red balls. In the $i$-th of these operations, he placed $RC_i$ red balls at coordinates $(RX_i,RY_i)$. Then, he performed another $N$ operations to place blue balls. In the $i$-th of these operations, he placed $BC_i$ blue balls at coordinates $(BX_i,BY_i)$. The total number of red balls placed and the total number of blue balls placed are equal , that is, $\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$. Let this value be $S$.
Snuke will now form $S$ pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the score of a pair of a red ball at coordinates $(rx, ry) $ and a blue ball at coordinates $(bx, by)$ as $|rx-bx| + |ry-by|$.
Snuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.
Constraints
- $1 \leq N \leq 1000$
- $0 \leq RX_i,RY_i,BX_i,BY_i \leq 10^9$
- $1 \leq RC_i,BC_i \leq 10$
- $\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $RX_1$ $RY_1$ $RC_1$ $RX_2$ $RY_2$ $RC_2$ $\vdots$ $RX_N$ $RY_N$ $RC_N$ $BX_1$ $BY_1$ $BC_1$ $BX_2$ $BY_2$ $BC_2$ $\vdots$ $BX_N$ $BY_N$ $BC_N$
Output
Print the maximum possible sum of the scores of the pairs.
Sample Input 1
2 0 0 1 3 2 1 2 2 1 5 0 1
Sample Output 1
8
If we pair the red ball at coordinates $(0,0)$ and the blue ball at coordinates $(2,2)$, the score of this pair is $|0-2| + |0-2|=4$ . Then, if we pair the red ball at coordinates $(3,2)$ and the blue ball at coordinates $(5,0)$, the score of this pair is $|3-5| + |2-0| =4$. Making these two pairs results in the total score of $8$, which is the maximum result.
Sample Input 2
3 0 0 1 2 2 1 0 0 2 1 1 1 1 1 1 3 3 2
Sample Output 2
16
Snuke may have performed multiple operations at the same coordinates.
Sample Input 3
10 582463373 690528069 8 621230322 318051944 4 356524296 974059503 6 372751381 111542460 9 392867214 581476334 6 606955458 513028121 5 882201596 791660614 9 250465517 91918758 3 618624774 406956634 6 426294747 736401096 5 974896051 888765942 5 726682138 336960821 3 715144179 82444709 6 599055841 501257806 6 390484433 962747856 4 912334580 219343832 8 570458984 648862300 6 638017635 572157978 10 435958984 585073520 7 445612658 234265014 6
Sample Output 3
45152033546
Manhattan Max Matching
Manhattan distance is actually quite difficult to deal with. Consider removing the absolute value and converting it into Chebyshev distance.
\[D=|x_1-x_2| + |y_1-y_2|=\max(|(x_1-y_1)-(x_2-y_2)|,|(x_1 + y_1)-(x_2 + y_2)|)) \]
This seems to require maximum cost and maximum flow, but in fact we are more accustomed to minimum cost and maximum flow. In addition, the question also asks for the minimum value, so consider taking the negative value.
\[D=-min((x_1-y_1)-(x_2-y_2),(x_1 + y_1)-(x_2 + y_2),(x_2 + y_2)-(x_1 + y_1),(x_2-y_2)-( x_1-y_1)) \]
So at this time we require a matching that minimizes the sum of min of the following four formulas. Since it is matched, consider the network flow.
First, the routine is to connect edges from the source point to each left node with flow rate \(RC_i\), and connect edges from each right node to the sink point with flow rate \(BC_i\).
Then consider how to find the minimum values of the next four things. Create four virtual nodes\(s_1,s_2,s_3,s_4\), and then each left node\(i\) is connected to \(s_1\) with an edge of cost\(RX_i-RY_i\), to \(s_2 \) Connect an edge with cost \(RY_i-RX_i\), and the same applies to the others. Then connect an edge with a cost of \(BY_i-BX_i\) from \(s_1\) to the right node, and an edge with a cost of \(BX_i-BY_i\) to \(s_2\). The same goes for the others. All edge flows mentioned in this paragraph are infinite.
Then you will find that the shortest path from point \(i\) to \(j\) is exactly \(|RX_i-BX_i| + |RY_i-BY_i|\). But it has so many sides, how can he only take the shortest path? When he finds that the flow with the smallest cost and the largest flow is running, he will naturally take the shortest path. So don’t think about it.
However, it is a very bad thing to have a negative connection cost, which indicates that a negative cycle may occur. So consider adding the same number to them all. But does this affect the final answer? In fact, it is not possible, because it is found that if \(INF\) is added to them in the calculation, then \(INF\) will be calculated \(2*S\) times in total. So the final subtraction is OK.
Remember to take the negative.
#include<bits/stdc + + .h>
using namespace std;
typedef long long LL;
const int N=4005,T=4000,S1=3999,S2=3998,S3=3997,S4=3996;
const LL INFLL=1e18,INF=2e9 + 5;
int n,hd[N],e_num(1),vhd[N],q[N*N],l,r,v[N],s;
LL d[N],ans;
struct edge{
int v,nxt,f;
L w;
}e[N<<3];
int bfs()
{
memcpy(hd,vhd,sizeof(hd));
memset(v,0,sizeof(v));
memset(d,0x7f,sizeof(d));
d[q[l=r=1]=0]=1,v[0]=1;
// printf("%d\
",hd[0]);
while(l<=r)
{
// printf("%d\
",q[l]);
for(int i=hd[q[l]];i;i=e[i].nxt)
{
if(d[e[i].v]>d[q[l]] + e[i].w & amp; & amp;e[i].f)
{
d[e[i].v]=d[q[l]] + e[i].w;
if(!v[e[i].v])
v[q[ + + r]=e[i].v]=1;
}
}
v[q[l + + ]]=0;
}
// printf("%lld\
",d[T]);
return d[T]<=INFLL;
}
int dfs(int x,int s)
{
// printf("%d %d\
",x,s);
if(x==T)
return s;
v[x]=1;
LL g;
for(int & amp;i=hd[x];i;i=e[i].nxt)
{
if(e[i].f & amp; & amp;!v[e[i].v] & amp; & amp;d[e[i].v]==d[x] + e[i] .w & amp; & amp;(g=dfs(e[i].v,min(s,e[i].f))))
{
e[i].f-=g;
e[i^1].f + =g;
ans + =e[i].w*g;
return g;
}
}
return 0;
}
void add_edge(int u,int v,int f,LL w)
{
e[ + + e_num]=(edge){v,hd[u],f,w};
hd[u]=e_num;
e[ + + e_num]=(edge){u,hd[v],0,-w};
hd[v]=e_num;
}
int main()
{
scanf("%d", & amp;n);
for(int i=1,x,y,c;i<=n;i + + )
{
scanf("%d%d%d", & amp;x, & amp;y, & amp;c),add_edge(0,i,c,0),s + =c;
add_edge(i,S1,INF,INF + x + y);
add_edge(i,S2,INF,INF + x-y);
add_edge(i,S3,INF,INF-x-y);
add_edge(i,S4,INF,INF + y-x);
}
for(int i=1,x,y,c;i<=n;i + + )
{
scanf("%d%d%d", & amp;x, & amp;y, & amp;c),add_edge(i + n,T,c,0);
add_edge(S1,i + n,INF,INF-x-y);
add_edge(S2,i + n,INF,INF + y-x);
add_edge(S3,i + n,INF,INF + x + y);
add_edge(S4,i + n,INF,INF + x-y);
}
memcpy(vhd,hd,sizeof(hd));
while(bfs())
while(dfs(0,INF));
printf("%lld",2LL*INF*s-ans);
return 0;
}