[图论记录]AT2672 [AGC018C] Coins
command_block
2021-11-19 08:43:04
**题意** ： 有 $x+y+z$ 个人，第 $i$ 个人有权值 $a_i,b_i,c_i$ 个铜币。
你需要将他们划分为三组 $S_A,S_B,S_C$ ，满足 $|S_A|=x,|S_B|=y,|S_C|=z$ 。
最大化 $\sum\limits_{u\in S_A}a_u+\sum\limits_{u\in S_B}b_u+\sum\limits_{u\in S_C}c_u$ 。
$x+y+z\leq 10^5$ ，时限 $\texttt{2s}$。
------------
这个问题显然是多重带权匹配，可以用费用流解决。建图如下：
使用模拟费用流。这里我们模拟 EK 算法的过程。
- **定理①** ：增广路不会重复经过某点。
- **定理②** ：和 $S,T$ 直接相连的边不会退流。
根据 EK 这是显然的。
我们记上半部的三个点分别为 $A,B,C$ ，考虑以下边：
- 若 $x$ 还有剩余，连 $S\to A$ 。 $B,C$ 类似。
- 残量网络中路径 $A\to T,B\to T,C\to T$ 的最大权值
即尚未占用的元素的 $a,b,c$ 的最大值。
根据 定理② 可以证明被占用的元素不会取消占用，于排序后是指针单调扫即可维护。
- 残量网络中 $A\to B,B\to A,A\to C,C\to A,B\to C,C\to B$ （中间不经过 $A,B,C$ 之一）的最大权值
以 $A\to B$ 为例，路径一定形如 $A\to u\to B$ ，这要求 $u$ 原来是匹配给 $B$ 的。最优权值即为 $\max\limits_{u\in S_B}a_u-b_u$ 。
可以用堆维护。
由于增广路必然经过 $A,B,C$ 三者之一（且不会重复经过），我们在这张小图上跑 SPFA 就可以得到增广路。
复杂度 $O(n\log n)$ ，常数较大。
显然可以扩展到划分为 $k$ 组的情况。复杂度是 $O(nk^2\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define ll long long
#define Pr pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define MaxN 100500
#define MaxK 5
using namespace std;
const ll INF=1ll<<60;
const int k=3;
vector<int> g[MaxK],l[MaxK];
int adl(int u,int v,int w)
{g[u].push_back(v);l[u].push_back(w);}
ll dis[MaxN];int pre[MaxN];bool in[MaxN];
void spfa(int s,int n)
{
queue<int> q;
for (int i=1;i<=n;i++){dis[i]=-INF;in[i]=0;}
dis[s]=0;in[s]=1;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();in[u]=0;
for (int i=0,v;i<g[u].size();i++)
if (dis[v=g[u][i]]<dis[u]+l[u][i]){
dis[v]=dis[pre[v]=u]+l[u][i];
if (!in[v]){in[v]=1;q.push(v);}
}
}
}
int n,w[MaxN][MaxK],cap[MaxK],fl[MaxN];
struct Heap{
int e;priority_queue<Pr> a;
void push(const Pr &x){a.push(x);}
void chk(){while(!a.empty()&&fl[a.top().sec]!=e)a.pop();}
bool empty(){chk();return a.empty();}
Pr top(){chk();return a.top();}
void pop(){chk();a.pop();}
}q[MaxK][MaxK];
void chg(int x,int c){
fl[x]=c;
for (int i=1;i<=k;i++)if (i!=c)
q[i][c].push(mp(w[x][i]-w[x][c],x));
}
int main()
{
for (int i=1;i<=k;i++){
scanf("%d",&cap[i]);
n+=cap[i];
for (int j=1;j<=k;j++)q[i][j].e=j;
q[i][i].e=0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++){
scanf("%d",&w[i][j]);
q[j][j].push(mp(w[i][j],i));
}
ll ans=0;
while(n--){
int S=k+1,T=k+2;
for (int i=1;i<=k;i++){
if (cap[i])adl(S,i,0);
if (!q[i][i].empty())adl(i,T,q[i][i].top().fir);
}
for (int i=1;i<=k;i++)
for (int j=1;j<=k;j++)if (i!=j&&!q[i][j].empty())
adl(i,j,q[i][j].top().fir);
spfa(S,T);ans+=dis[T];
int p[MaxK],tn=0;
for (int u=T;u;u=pre[u])p[++tn]=u;
for (int i=1;i<tn;i++){
int u=p[i+1],v=p[i];
if (v==T)chg(q[u][u].top().sec,u);
else if (u==S)cap[v]--;
else chg(q[u][v].top().sec,u);
}
for (int i=1;i<=T;i++){g[i].clear();l[i].clear();}
}printf("%lld",ans);
return 0;
}
```