CF1107F Vasya and Endless Credits

4 0 0

KM 做法这么简单好想为什么都在 dp？~~我第一次过也是用的 dp。~~

建模非常好想，每天只能收一次钱，最简单的思路是我们枚举第几天开车跑路，但是再一想我们不关心是第几天，只关心每次贷款离开车跑路还差几天，于是我们从 i 向 j 连边，边权是 ai+bi×min(ki,j)，意义为第 i 种贷款离买车还差 j 天对答案的贡献，当然我们实现时需要对 0 取最大值，因为取 0 的意义为不参与答案贡献，然而我们并不要求在最后一天开车，所以对 0 取最大值是必要的。

并且，容易证明我们不可能在某一天没有进行任何操作。

所以建完模直接跑 KM 算法即可，时间复杂度 O(n3)。

代码：

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 10000000000000000
#define pii pair <int, int>
using namespace std;
constexpr int N = 505, P = 1e9 + 7;
inline int rd ()
{
	int x = 0, f = 1;
	char ch = getchar ();
	while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
	while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
	return x * f;
}
int n, sum, ans;
int e[N][N];
int lx[N], ly[N], px[N], py[N], pre[N], slack[N];
bool vx[N], vy[N], flag;
int a[N], b[N], k[N];
queue <int> q;
void aug (int v)
{
  while (v)
  {
    int t = px[pre[v]];
    px[pre[v]] = v;
    py[v] = pre[v];
    v = t;
  }
}
void bfs (int s)
{
  memset (vx, 0, sizeof vx);
  memset (vy, 0, sizeof vy);
  memset (slack, 127, sizeof slack);
  while (! q.empty ()) q.pop ();
  q.push (s);
  while (true)
  {
    while (! q.empty ())
    {
      int u = q.front ();
      q.pop ();
      vx[u] = 1;
      rep (i, 1, n)
      {
        if (vy[i]) continue;
        if (lx[u] + ly[i] - e[u][i] < slack[i])
        {
          slack[i] = lx[u] + ly[i] - e[u][i];
          pre[i] = u;
          if(! slack[i])
          {
            vy[i] = 1;
            if (! py[i])
            {
              aug (i); return ;
            } else q.push (py[i]);
          }
        }  
      } 
    }
    int d = linf;
    rep (i, 1, n) if (! vy[i]) d = min (d, slack[i]);
    rep (i, 1, n)
    {
      if (vx[i]) lx[i] -= d, sum -= d;
      if (vy[i]) ly[i] += d, sum += d;
      else slack[i] -= d;
    }
    rep (i, 1, n)
    {
      if (vy[i]) continue;
      if(! slack[i])
      {
        vy[i] = 1;
        if (! py[i])
        {
          aug (i); return ;
        } else q.push (py[i]);
      }
    }
  }
}
void solve ()
{
  memset (lx, -127, sizeof lx);
  sum = 0;
  rep (i, 1, n) rep (j, 1, n) lx[i] = max (lx[i], e[i][j]);
  rep (i, 1, n) sum += lx[i];
  
  rep (i, 1, n)
    bfs (i);
}
signed main ()
{
  n = rd ();
  rep (i, 1, n)
  {
    a[i] = rd (), b[i] = rd (), k[i] = rd ();
  }
  rep (i, 1, n)
    rep (j, 1, n)
      e[i][j] = max (0ll, a[i] - min (k[i], j - 1) * b[i]);
  solve ();
  printf ("%lld
", sum);
}
/*

*/

# 随笔