題目描述

給定實直線 \(L\) 上 \(n\) 個開區(qū)間組成的集合 \(I\) ，和一個正整數(shù) \(k\) ，試設計一個算法，從開區(qū)間集合 \(I\) 中選取出開區(qū)間集合 \(S \subseteq I\) ，使得在實直線 \(L\) 的任何一點 \(x\) ，\(S\) 中包含點 \(x\) 的開區(qū)間個數(shù)不超過 \(k\) 。且 \(\sum\limits_{z \in S} | z |\) 達到最大。這樣的集合 \(S\) 稱為開區(qū)間集合 \(I\) 的最長 \(k\) 可重區(qū)間集。\(\sum\limits_{z \in S} | z |\) 稱為最長 \(k\) 可重區(qū)間集的長度。

對于給定的開區(qū)間集合 \(I\) 和正整數(shù) \(k\) ，計算開區(qū)間集合 \(I\) 的最長 \(k\) 可重區(qū)間集的長度。

輸入格式

文件的第 \(1\) 行有 \(2\) 個正整數(shù) \(n\) 和 \(k\) ，分別表示開區(qū)間的個數(shù)和開區(qū)間的可重迭數(shù)。

接下來的 \(n\) 行，每行有 \(2\) 個整數(shù) \(l_i\) 和 \(r_i\) ，表示開區(qū)間的左右端點坐標，注意可能有 \(l_i > r_i\) ，此時請將其交換。

輸出格式

輸出最長 \(k\) 可重區(qū)間集的長度。

樣例

樣例輸入

4 2 1 7 6 8 7 10 9 13

樣例輸出

15

數(shù)據(jù)范圍與提示

\(1 \leq n \leq 500, 1 \leq k \leq 3\)

題解

先離散化

然后每個點向后面一個點連容量為 \(inf\) ，費用為 \(0\) 的邊

對于一個區(qū)間 \(l,r\) ，從 \(l\) 連向 \(r\) ，容量為 \(1\) ，費用為其長度的相反數(shù)，代表一個區(qū)間只能選一次，選一次的貢獻為它的長度

這樣建模跑費用流就可以使答案最大

但是還有每個點只能被覆蓋 \(k\) 的限制

那么源點向 \(1\) 號點連容量為 \(k\) ，費用為 \(0\) 的邊

\(n\) 號點向匯點連容量為 \(k\) ，費用為 \(0\) 的邊

在一次增廣中，每個點都只會被經(jīng)過一次

那么最大流一定為 \(k\) ，即 \(k\) 次增廣，所以每個點只會被經(jīng)過 \(k\) 次，滿足題目限制

#include<bits/stdc++.h> #define ui unsigned int #define ll long long #define db double #define ld long double #define ull unsigned long long const int MAXN=1000+10,MAXM=(MAXN<<1),inf=0x3f3f3f3f; int n,k,e=1,beg[MAXN],cur[MAXN],L[MAXN],R[MAXN],r,level[MAXN],p[MAXN],vis[MAXN],clk,s,t,nex[MAXM<<1],to[MAXM<<1],cap[MAXM<<1],was[MAXM<<1],val[MAXN]; ll answas; std::queue<int> q; std::vector<int> V; std::map<int,int> M; template<typename T> inline void read(T &x) {T data=0,w=1;char ch=0;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();x=data*w; } template<typename T> inline void write(T x,char ch='\0') {if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');if(ch!='\0')putchar(ch); } template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);} template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);} template<typename T> inline T min(T x,T y){return x<y?x:y;} template<typename T> inline T max(T x,T y){return x>y?x:y;} inline void insert(int x,int y,int z,int w) {to[++e]=y;nex[e]=beg[x];beg[x]=e;cap[e]=z;was[e]=w;to[++e]=x;nex[e]=beg[y];beg[y]=e;cap[e]=0;was[e]=-w; } inline void discretization() {for(register int i=1;i<=n;++i)V.push_back(L[i]),V.push_back(R[i]);std::sort(V.begin(),V.end());V.erase(std::unique(V.begin(),V.end()),V.end());for(register int i=0,lt=V.size();i<lt;++i)M[V[i]]=i+1;for(register int i=1;i<=n;++i)L[i]=M[L[i]],R[i]=M[R[i]],chkmax(r,R[i]); } inline bool bfs() {memset(level,inf,sizeof(level));level[s]=0;p[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();p[x]=0;for(register int i=beg[x];i;i=nex[i])if(cap[i]&&level[to[i]]>level[x]+was[i]){level[to[i]]=level[x]+was[i];if(!p[to[i]])p[to[i]]=1,q.push(to[i]);}}return level[t]!=inf; } inline int dfs(int x,int maxflow) {if(x==t||!maxflow)return maxflow;vis[x]=clk;int res=0;for(register int &i=cur[x];i;i=nex[i])if((vis[to[i]]^vis[x])&&cap[i]&&level[to[i]]==level[x]+was[i]){int f=dfs(to[i],min(maxflow,cap[i]));res+=f;cap[i]-=f;cap[i^1]+=f;maxflow-=f;answas+=1ll*was[i]*f;if(!maxflow)break;}vis[x]=0;return res; } inline void MCMF() {while(bfs())clk++,memcpy(cur,beg,sizeof(cur)),dfs(s,inf); } int main() {read(n);read(k);for(register int i=1;i<=n;++i){read(L[i]);read(R[i]);if(L[i]>R[i])std::swap(L[i],R[i]);val[i]=R[i]-L[i];}discretization();s=r+1,t=s+1;insert(s,1,k,0);insert(r,t,k,0);for(register int i=1;i<r;++i)insert(i,i+1,inf,0);for(register int i=1;i<=n;++i)insert(L[i],R[i],1,-val[i]);MCMF();write(-answas,'\n');return 0; }

轉載于:https://www.cnblogs.com/hongyj/p/9433635.html

總結

以上是生活随笔為你收集整理的【刷题】LOJ 6014 「网络流 24 题」最长 k 可重区间集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。