【网络流24题】最长k可重区间集问题

这是一道我一开始没想出来的题。

题面

https://www.luogu.org/problemnew/show/P3358

题解

离散化。

图的基础是一条长链，流量为$k$，区间是从$l$指向$r$的边，流量为$1$，费用为长度。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ri register int
#define N 5000
#define S 0
#define INF 1000000007
using namespace std;

int n,k,T;
int l[550],r[550],v[550],dc[1450];
int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch>'9' || ch<'0') f|=(ch=='-'),ch=getchar();
  while (ch>='0' && ch<='9') ret*=10,ret+=(ch-'0'),ch=getchar();
  return f?-ret:ret;
}

struct graph {
  vector<int> to,w,c;
  vector<int> ed[N];
  int dis[N]; int cur[N]; bool vis[N];
  void add_edge(int a,int b,int aw,int ac) {
    to.push_back(b); w.push_back(aw); c.push_back(ac);  ed[a].push_back(to.size()-1);
    to.push_back(a); w.push_back(0);  c.push_back(-ac); ed[b].push_back(to.size()-1);
  }
  bool spfa() {
    memset(dis,-0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    dis[S]=0;q.push(S);vis[S]=1;
    while (!q.empty()) {
      int x=q.front(); q.pop();
      for (ri i=0;i<ed[x].size();i++) {
        int e=ed[x][i];
        if (dis[to[e]]<dis[x]+c[e] && w[e]) {
          dis[to[e]]=dis[x]+c[e];
          if (!vis[to[e]]) vis[to[e]]=1,q.push(to[e]);
        }
      }
      vis[x]=0;
    }
    return dis[T]>-INF;
  }
  int dfs(int x,int lim) {
    if (x==T || !lim) return lim;
    int sum=0; vis[x]=1;
    for (ri &i=cur[x];i<ed[x].size();i++) {
      int e=ed[x][i];
      if (dis[x]+c[e]==dis[to[e]] && w[e] && !vis[to[e]]) {
        int f=dfs(to[e],min(lim,w[e]));
        w[e]-=f; w[1^e]+=f;
        lim-=f; sum+=f;
        if (!lim) return sum;
      }
    }
    return sum;
  }
  int zkw() {
    int ret=0;
    while (spfa()) {
      memset(vis,0,sizeof(vis));
      memset(cur,0,sizeof(cur));
      ret+=dis[T]*dfs(S,INF);
    }
    return ret;
  }
} G;

int main() {
  n=read(); k=read();
  int cc=0;
  for (ri i=1;i<=n;i++) {
    l[i]=read(); r[i]=read();
    if (l[i]>r[i]) swap(l[i],r[i]);
    v[i]=r[i]-l[i];
    dc[++cc]=l[i]; dc[++cc]=r[i];
  }
  sort(dc,dc+cc+1);
  cc=unique(dc,dc+cc+1)-dc;
  for (ri i=1;i<=n;i++) {
    l[i]=lower_bound(dc,dc+cc+1,l[i])-dc;
    r[i]=lower_bound(dc,dc+cc+1,r[i])-dc;
  }
  T=cc+1;
  G.add_edge(S,1,k,0);
  for (ri i=1;i<cc;i++) G.add_edge(i,i+1,k,0);
  G.add_edge(cc,T,k,0);
  for (ri i=1;i<=n;i++) G.add_edge(l[i],r[i],1,v[i]);
  cout<<G.zkw()<<endl;
  return 0;
}