【网络流24题】最长k可重区间集(费用流)
网络 24 最长 区间 费用
2023-09-11 14:14:41 时间
【网络流24题】最长k可重区间集(费用流)
题面
题解
首先注意一下
这道题目里面
在Cogs上直接做就行了
洛谷和Loj上需要判断数据合法,如果\(l>r\)就要交换\(l,r\)
首先离散化
数据范围比较大
记录一下\(l,r\)和区间大小
这个问题可以换一种看法
相当于从源点出发,走K次,
问你路径的最大权值和
其中有些边可以无限制的走,但是它们的长度为0
所以从源点开始到汇点,挂出一条链来
容量为K,费用为0
这些路是可以随便走的
另外,还有若干个区间
但是每个只能走一次
因此,直接把相应的区间连起来,容量为1,费用为长度
这样的话,控制了流最多为K
跑一边最大费用流就是答案啦
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 5000
#define MAXL 500000
#define INF 1000000000
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next,w,fy;
}e[MAXL];
bool vis[MAX];
int h[MAX],cnt=2;
inline void Add(int u,int v,int w,int fy)
{
e[cnt]=(Line){v,h[u],w,fy};h[u]=cnt++;
e[cnt]=(Line){u,h[v],0,-fy};h[v]=cnt++;
}
int pe[MAX],pr[MAX],dis[MAX];
int S,T,Cost,n,m,Flow,opt=-1;
bool SPFA()
{
memset(dis,63,sizeof(dis));
queue<int> Q;
Q.push(S);dis[S]=0;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w&&dis[v]>dis[u]+e[i].fy)
{
dis[v]=dis[u]+e[i].fy;
pe[v]=i;pr[v]=u;
if(!vis[v])vis[v]=true,Q.push(v);
}
}
vis[u]=false;
}
if(dis[T]>=INF)return false;
int flow=INF;
for(int i=T;i!=S;i=pr[i])flow=min(flow,e[pe[i]].w);
for(int i=T;i!=S;i=pr[i])e[pe[i]].w-=flow,e[pe[i]^1].w+=flow;
Cost+=opt*flow*dis[T];
Flow+=flow;
return true;
}
struct I{int l,r,v;}q[MAX];
int Sta[MAX],tot=0,K;
int main()
{
freopen("interv.in","r",stdin);
freopen("interv.out","w",stdout);
n=read();K=read();
for(int i=1;i<=n;++i)
{
q[i].l=read();q[i].r=read();
if(q[i].l>q[i].r)swap(q[i].l,q[i].r);
q[i].v=q[i].r-q[i].l;
Sta[++tot]=q[i].l;Sta[++tot]=q[i].r;
}
sort(&Sta[1],&Sta[tot+1]);
tot=unique(&Sta[1],&Sta[tot+1])-Sta-1;
for(int i=1;i<=n;++i)
{
q[i].l=lower_bound(&Sta[1],&Sta[tot+1],q[i].l)-Sta;
q[i].r=lower_bound(&Sta[1],&Sta[tot+1],q[i].r)-Sta;
}
S=0;T=tot+1;
for(int i=0;i<T;++i)Add(i,i+1,K,0);
for(int i=1;i<=n;++i)Add(q[i].l,q[i].r,1,-q[i].v);
while(SPFA());
printf("%d\n",Cost);
return 0;
}
相关文章
- 【黑马Android】(05)短信/查询和添加/内容观察者使用/子线程网络图片查看器和Handler消息处理器/html查看器/使用HttpURLConnection采用Post方式请求数据/开源项目
- 使用 CoreTelephony 框架获取当前网络运营商
- 判断网络状态工具类
- [YOLOv7/YOLOv5系列算法改进NO.13]主干网络C3替换为轻量化网络EfficientNetv2
- Atitit 网络存储协议 远程存储协议 目录 1. Email类1 1.1. Eas Exchange Activesync介绍1 1.2. Imap pop31 2. 网盘类远程存储web
- 为App所在的进程指定网络
- jittor和pytorch生成网络对比之dragan
- 【第53篇】MAFormer: 基于多尺度注意融合的变压器网络视觉识别
- 实践案例丨GaussDB网络重传/丢包问题定位总结
- 基于DNN网络的信道估计matlab仿真,仿真输出信道估计值的mse指标
- Qemu之Network Device全虚拟方案一:前端网络流的建立
- Swarm使用原生的overlay网络
- 网络命令大全
- Linux tracepath跟踪路径到沿着该路径发现MTU的网络主机
- 蝴蝶网络 Butterfly network
- 手把手教你用Python网络爬虫获取壁纸图片
- win10配置显示隐藏网络