#6014. 「网络流 24 题」最长 k 可重区间集
题目描述
给定实直线 L LL 上 n nn 个开区间组成的集合 I II，和一个正整数 k kk，试设计一个算法，从开区间集合 I II 中选取出开区间集合 S⊆I S \subseteq IS⊆I，使得在实直线 L LL 的任何一点 x xx，S SS 中包含点 x xx 的开区间个数不超过 k kk。且 ∑z∈S∣z∣ \sum\limits_{z \in S} | z |z∈S∑∣z∣ 达到最大。这样的集合 S SS 称为开区间集合 I II 的最长 k kk 可重区间集。∑z∈S∣z∣ \sum\limits_{z \in S} | z |z∈S∑∣z∣ 称为最长 k kk 可重区间集的长度。
对于给定的开区间集合 I II 和正整数 k kk，计算开区间集合 I II 的最长 k kk 可重区间集的长度。
输入格式
文件的第 1 11 行有 2 22 个正整数 n nn 和 k kk，分别表示开区间的个数和开区间的可重迭数。
接下来的 n nn 行，每行有 2 22 个整数 li l_ili 和 ri r_iri，表示开区间的左右端点坐标，注意可能有 li>ri l_i > r_ili>ri，此时请将其交换。
输出格式
输出最长 k kk 可重区间集的长度。
样例
样例输入
4 2
1 7
6 8
7 10
9 13样例输出
15数据范围与提示
1≤n≤500,1≤k≤3 1 \leq n \leq 500, 1 \leq k \leq 31≤n≤500,1≤k≤3
题目链接：https://loj.ac/problem/6014
题意：中文题意，意思明显。
思路：当k=1时，这个问题等价于从n个区间选取一个元素互不相交的子集，目标是最大化子集权重和。这个问题又被称为区间图的最大权独立集。这个问题可以用dp算法求解,也可以看做是一个最短路问题（注意建图方式）。所以最长 k 可重区间集，即求k条最短路，费用流。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define PI acos(-1.0)
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;
const ll INF=1e18+;
struct edge
{
int from,to;
int cap,flow;
int w;
};
vector<edge>es;
vector<int>G[maxn];
int pre[maxn];
int dist[maxn];
inline void init(int n)
{
es.clear();
for(int i=; i<=n+; i++) G[i].clear();
}
inline void addedge(int from,int to,int cap,int w)
{
es.push_back((edge)
{
from,to,cap,,w
});
es.push_back((edge)
{
to,from,,,-w
});
int num=es.size();
G[from].push_back(num-);
G[to].push_back(num-);
}
bool SPFA(int s,int t)
{
static queue<int>q;
static bool inq[maxn];
for(int i=; i<maxn; i++) inq[i]=false,dist[i]=inf;
dist[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int i=; i<G[u].size(); i++)
{
edge e=es[G[u][i]];
if(e.cap>e.flow&&dist[e.to]>dist[u]+e.w)
{
pre[e.to]=G[u][i];
dist[e.to]=dist[u]+e.w;
if(!inq[e.to]) q.push(e.to),inq[e.to]=true;
}
}
}
return dist[t]<inf;
}
void dinic(int s,int t,int f)
{
int flow=,cost=;
while(SPFA(s,t))
{
int d=f;
for(int i=t; i!=s; i=es[pre[i]].from)
d=min(d,es[pre[i]].cap-es[pre[i]].flow);
f-=d;
flow+=d;
cost+=d*dist[t];
if(f<=) break;
for(int i=t; i!=s; i=es[pre[i]].from)
es[pre[i]].flow+=d,es[pre[i]^].flow-=d;
}
printf("%d\n",-cost);
}
int l[maxn],r[maxn],w[maxn];
int c[maxn<<];
int compress(int n)
{
memcpy(c+,l+,sizeof(l));
memcpy(c+n+,r+,sizeof(r));
sort(c+,c+*n+);
int SIZE=unique(c+,c+*n+)-(c+);
for(int i=; i<=n; i++)
{
l[i]=lower_bound(c+,c+SIZE,l[i])-c;
r[i]=lower_bound(c+,c+SIZE,r[i])-c;
}
return SIZE;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=; i<=n; i++)
{
scanf("%d%d",&l[i],&r[i]);
if(r[i]<l[i]) swap(l[i],r[i]);
w[i]=r[i]-l[i];
}
int s=,t=compress(n);
for(int i=; i<t; i++)
addedge(i,i+,inf,);
for(int i=; i<=n; i++)
{
///cout<<l[i]<<" * "<<r[i]<<" * "<<w[i]<<endl;
addedge(l[i],r[i],1,-w[i]);
}
dinic(s,t,k);
return ;
}
最小费用流