「网络流24题」最长k可重区间集问题
搬运byvoid的题解
「问题分析」
最大权不相交路径问题，可以用最大费用最大流解决。
「建模方法」
方法1
按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S’。
1、连接S到S’一条容量为K，费用为0的有向边。
2、从S’到每个<i.a>连接一条容量为1，费用为0的有向边。
3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。
4、从每个顶点<i.a>到<i.b>连接一条容量为1，费用为区间长度的有向边。
5、对于每个区间i，与它右边的不相交的所有区间j各连一条容量为1，费用为0的有向边。
求最大费用最大流，最大费用流值就是最长k可重区间集的长度。
方法2
离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。
1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。
4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。
求最大费用最大流，最大费用流值就是最长k可重区间集的长度。
「建模分析」
这个问题可以看做是求K条权之和最大的不想交路径，每条路径为一些不相交的区间序列。由于是最大费用流，两条路径之间一定有一些区间相交，可以看做事相交部分重复了2次，而K条路经就是最多重复了K次。最简单的想法就是把区间排序后，不相交的区间之间连接一条边，由于每个区间只能用一次，所以要拆点，点内限制流量。如果我们改变一下思路，把端点作为网络中的顶点，区间恰恰是特定一些端点之间的边，这样建模的复杂度更小。方法1的边数是O(N^2)的，而方法2的边数是O(N)的，可以解决更大规模的问题。
我写的是方法2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<set> #define ll long long #define mod 1000000007 #define inf 1000000000 using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans; int T,n,K,top,cnt=1; int l[505],r[505],t[505]; int disc[1005]; int last[1005],q[1005],d[1005]; bool inq[1005],mark[1005]; struct edge{ int to,next,v,c; }e[100005]; void insert(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { memset(d,-1,sizeof(d)); int head=0,tail=1; q[0]=T;d[T]=0; while(head!=tail) { int now=q[head];head++;inq[now]=0; if(head==1005)head=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].v&&d[now]+e[i^1].c>d[e[i].to]) { d[e[i].to]=d[now]+e[i^1].c; if(!inq[e[i].to]) { q[tail++]=e[i].to; if(tail==1005)tail=0; inq[e[i].to]=1; } } } return d[0]!=-1; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(e[i].v&&!mark[e[i].to]&&d[x]-e[i].c==d[e[i].to]) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; ans+=w*e[i].c; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); dfs(0,inf); } } } void build() { T=2*n+1; insert(0,1,K,0);insert(2*n,T,K,0); for(int i=1;i<2*n;i++)insert(i,i+1,inf,0); for(int i=1;i<=n;i++) insert(l[i],r[i],1,t[i]); } int main() { n=read();K=read(); for(int i=1;i<=n;i++) { l[i]=read(),r[i]=read();t[i]=r[i]-l[i]; disc[++top]=l[i];disc[++top]=r[i]; } sort(disc+1,disc+top+1); for(int i=1;i<=n;i++) { l[i]=lower_bound(disc+1,disc+top+1,l[i])-disc; r[i]=lower_bound(disc+1,disc+top+1,r[i])-disc; } build(); zkw(); printf("%d\n",ans); return 0; } |
OI 课件=>
3 2
1 5 //(1,5)=[2, 4]
4 6 //(4,6)={5}
4 7 //(4,7)=[5,6]
全部可以选啊，答案应该是4+2+3=9吧
(1,5)和(4,6)是重合的TAT，不仅是点不重合而且线段也不能重合