首页 > 代码库 > 【网络流24题】No.21 （最长 k 可重区间集问题 最长不相交路径 最大费用流）

【网络流24题】No.21 （最长 k 可重区间集问题 最长不相交路径 最大费用流）

2024-08-19 14:40:05   219人阅读

【】

　　技术分享

 

输入文件示例
input.txt
4 2
1 7
6 8
7 10
9 13

输出文件示例
output.txt
15

 

 

【分析】

　　直接co题解好了，写得挺全。。

【建模方法】

方法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)的，可以解决更大规模的问题。

 

 

感觉我的数据错了hhh

技术分享 
  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 #define Maxn 101000
 10 #define INF 0xfffffff
 11 
 12 struct node
 13 {
 14     int x,y,f,o,c,next;
 15 }t[Maxn*10];int len;
 16 int first[Maxn];
 17 
 18 int mymin(int x,int y) {return x<y?x:y;}
 19 int mymax(int x,int y) {return x>y?x:y;}
 20 
 21 void ins(int x,int y,int f,int c)
 22 {
 23     t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;
 24     t[len].next=first[x];first[x]=len;t[len].o=len+1;
 25     t[++len].x=y;t[len].y=x;t[len].f=0;t[len].c=-c;
 26     t[len].next=first[y];first[y]=len;t[len].o=len-1;
 27 }
 28 
 29 int st,ed;
 30 queue<int > q;
 31 int dis[Maxn],pre[Maxn],flow[Maxn];
 32 bool inq[Maxn];
 33 bool bfs()
 34 {
 35     while(!q.empty()) q.pop();
 36     // memset(dis,-1,sizeof(dis));
 37     for(int i=1;i<=ed;i++) dis[i]=-INF;
 38     memset(inq,0,sizeof(inq));
 39     q.push(st);dis[st]=0;flow[st]=INF;inq[st]=1;
 40     while(!q.empty())
 41     {
 42         int x=q.front();
 43         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 44         {
 45             int y=t[i].y;
 46             if(dis[y]<dis[x]+t[i].c)
 47             {
 48                 dis[y]=dis[x]+t[i].c;
 49                 pre[y]=i;
 50                 flow[y]=mymin(flow[x],t[i].f);
 51                 if(!inq[y])
 52                 {
 53                     inq[y]=1;
 54                     q.push(y);
 55                 }
 56             }
 57         }
 58         inq[x]=0;q.pop();
 59     }
 60     if(dis[ed]>-INF) return 1;
 61     return 0;
 62 }
 63 
 64 void output()
 65 {
 66     for(int i=1;i<=len;i+=2)
 67      printf("%d->%d %d %d\n",t[i].x,t[i].y,t[i].f,t[i].c);
 68     printf("\n");
 69 }
 70 
 71 int max_flow()
 72 {
 73     int ans=0,sum=0;
 74     while(bfs())
 75     {
 76         sum+=dis[ed]*flow[ed];
 77         ans+=flow[ed];
 78         int now=ed;
 79         while(now!=st)
 80         {
 81             t[pre[now]].f-=flow[ed];
 82             t[t[pre[now]].o].f+=flow[ed];
 83             now=t[pre[now]].x;
 84         }
 85     }
 86     return sum;
 87 }
 88 
 89 struct hp
 90 {
 91     int x,id;
 92 }tt[Maxn];int tl=0;
 93 int nx[Maxn],ny[Maxn],ln[Maxn];
 94 
 95 bool cmp(hp x,hp y) {return x.x<y.x;}
 96 
 97 void init()
 98 {
 99     int n,k;
100     scanf("%d%d",&n,&k);
101     len=0;
102     memset(first,0,sizeof(first));
103     int mx=0;
104     for(int i=1;i<=n;i++)
105     {
106         int x,y;
107         // scanf("%d%d",&x,&y);
108         // ins(x,y,1,y-x);
109         scanf("%d%d",&nx[i],&ny[i]);
110         ln[i]=ny[i]-nx[i];
111         tt[++tl].x=nx[i];tt[tl].id=i;
112         tt[++tl].x=ny[i];tt[tl].id=i+n;
113         // mx=mymax(mx,y);
114     }
115     sort(tt+1,tt+1+tl,cmp);
116     int pp=1;
117     int now=tt[1].x;tt[1].x=1;
118     for(int i=2;i<=tl;i++)
119     {
120         if(tt[i].x!=now) pp++,now=tt[i].x;
121         tt[i].x=pp;
122     }
123     for(int i=1;i<=tl;i++)
124     {
125         if(tt[i].id>n) ny[tt[i].id-n]=tt[i].x;
126         else nx[tt[i].id]=tt[i].x;
127     }
128     for(int i=1;i<=n;i++) ins(nx[i],ny[i],1,ln[i]);
129     mx=pp;
130     st=mx+1;ed=st+1;
131     ins(st,1,k,0);
132     for(int i=1;i<mx;i++) ins(i,i+1,k,0);
133     ins(mx,ed,k,0);
134 }
135 
136 int main()
137 {
138     init();
139     // output();
140     int ans;
141     ans=max_flow();
142     printf("%d\n",ans);
143     return 0;
144 }
View Code

 

 

2016-11-08 07:26:58

 

【网络流24题】No.21 （最长 k 可重区间集问题 最长不相交路径 最大费用流）


联系
我们