POJ 3680 Intervals

题目大意：给定一些开区间\((a_i,b_i)\)，以及区间的价值\(w_i\)。每个点最多被\(k\)个区间覆盖，要求最大化选取的区间的价值和。

非常神奇的费用流。

我们首先将点离散化，假设有\(m\)个点。然后建立超级源\(S\)和超级汇\(T\)。

首先连两条边\((S,1,k,0),(m,T,k,0)\)，然后相邻两点之间连边\((i,i+1,k,0)\)。然后对于区间\((a,b)\)，我们连\((a,b,1,-w)\)。求出最小费用流后取反。

要想搞懂这神奇的建边方式就要先搞懂它是如何满足“每个点最多被\(k\)个区间覆盖”这一限制的。在一个网络中，流入点\(i\)的流量\(flow\)就是\(i\)还可以被覆盖的次数，或者说\(i\)在之前被覆盖了\(k-flow\)次。当我们选择了区间\((a,b)\)后，\((a,b)\)这些节点的剩余流量都减少了，于是我们连\((a,b,1,-w)\)，将这部分流量分流出去。

这种带反悔的最优化问题就可以用费用流来高效解决。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define N 405using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,k;int cas;struct interval {    int x,y,w;}e[N];int d[N<<1];struct load {    int to,next;    int flow,c;}s[N<<2];int h[N],cnt;int S,T;void add(int i,int j,int flow,int c) {    s[++cnt]=(load) {j,h[i],flow,c};h[i]=cnt;    s[++cnt]=(load) {i,h[j],0,-c};h[j]=cnt;}int dis[N];queue
         
          q;bool in[N];int fr[N],edge[N];int ans;bool spfa() { memset(dis,0x3f,sizeof(dis)); dis[0]=0; q.push(0); while(!q.empty()) { int v=q.front();q.pop(); in[v]=0; for(int i=h[v];i;i=s[i].next) { int to=s[i].to; if(s[i].flow&&dis[to]>dis[v]+s[i].c) { dis[to]=dis[v]+s[i].c; fr[to]=v; edge[to]=i; if(!in[to]) { in[to]=1; q.push(to); } } } } if(dis[T]>1e9) return 0; int mn=1e9; for(int i=T;i;i=fr[i]) mn=min(mn,s[edge[i]].flow); for(int i=T;i;i=fr[i]) s[edge[i]].flow-=mn,s[edge[i]^1].flow+=mn; ans+=mn*dis[T]; return 1;}int main() { cas=Get(); while(cas--) { d[0]=0; n=Get(),k=Get(); for(int i=1;i<=n;i++) { int a=Get(),b=Get(),c=Get(); e[i]=(interval) {a,b,c}; d[++d[0]]=a; d[++d[0]]=b; } sort(d+1,d+1+d[0]); int cc=unique(d+1,d+1+d[0])-d; for(int i=1;i<=n;i++) { e[i].x=lower_bound(d+1,d+cc,e[i].x)-d; e[i].y=lower_bound(d+1,d+cc,e[i].y)-d; } T=cc; memset(h,0,sizeof(h)); cnt=1; add(S,1,k,0),add(T-1,T,k,0); for(int i=1;i