command_block 的博客

command_block 的博客

[图论记录]AT2672 [AGC018C] Coins

posted on 2021-11-19 08:43:04 | under 记录 |

题意 : 有 $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)$。

#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;
}