题解【CF730I Olympiad in Programming and Sports】

传送门。

$\texttt{Description}$

有 $n$ 个二元组 $(a_i,b_i)$，你需要将这 $n$ 个数分配到两个组，第一个组获得的价值是 $\sum a_i$，第二个组是 $\sum b_i$，每个组有一个容量，请你求出价值总和的最大值。

$1\le n\le 3\times 10^3$。

$\texttt{Solution}$

我焯怎么全都是反悔贪心啊，这不赤裸裸的费用流吗。

考虑一个二分图，左边是所有的二元组，右边两个点分别代表两个集合。

然后思路就十分的清晰了。

每个数只能进入一个集合中，所以令 $s\to i$ 连一条容量为 $1$，费用为 $0$ 的边。

然后每一个二元组分别向两个集合连容量为 $1$，费用为 $a_i$ 或 $b_i$ 的边。表示分配到某个集合可以获取相应的价值。

最后每个集合向 $t$ 连一条容量为该集合容量，费用为 $0$ 的边。

基本上算是费用流的板子题了。

输出方案只需要找流量为 $0$ 的边即可。

代码：

int main()
{
    n=read(),w1=read(),w2=read();
    s=0,t=n+3;
    for(register int i=1;i<=n;i++) a[i]=read();
    for(register int i=1;i<=n;i++) b[i]=read();
    for(register int i=1;i<=n;i++) add_edge(s,i,1,0);
    for(register int i=1;i<=n;i++) add_edge(i,n+1,1,a[i]),add_edge(i,n+2,1,b[i]);
    add_edge(n+1,t,w1,0),add_edge(n+2,t,w2,0);
    MCMF();
    return 0;
}

$$\texttt{The End.by UF}$$