北京集训区间覆盖费用流

第三题区间覆盖（Interval）
(Interval.pas\c\cpp）
【问题描述】
有N 个开区间(ai,bi)，每个区间有一个权值wi，现在请你选择其中的一些区
间，使得选出的区间权值总和最大，并满足数轴上的任意位置都被覆盖不超过K
次。

思路：最大费用最大流

先离散化

离散化后第i个点和i+1个点连一条容量为K，费用为0的边

对于每个区间 ai到bi连一条容量为1 费用为wi的边

费用流求之

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<map>
  7 using namespace std;
  8 #define MAXN 500
  9 #define MAXM 2000
 10 int T,n,K,m,top;
 11 struct node
 12 {
 13     int u,remain,cost;
 14     node *next,*inv;
 15 };
 16 struct interval
 17 {
 18     int x,y,w;
 19 }a[MAXN];
 20 int b[MAXN],Q[9000000],d[MAXN],f[MAXN];
 21 node *graph[MAXN],*edge[MAXN],memo[MAXM];
 22 bool use[MAXN];
 23 map<int,int> home;
 24 void add(int x,int y,int r,int cost)
 25 {
 26     node *p=&memo[top++],*q=&memo[top++];
 27     p->u=y; p->remain=r; p->cost=cost; p->next=graph[x]; graph[x]=p;
 28     q->u=x; q->remain=0; q->cost=-cost; q->next=graph[y]; graph[y]=q;
 29     p->inv=q; q->inv=p;
 30 }
 31     
 32 void build_graph()
 33 {
 34     int i;
 35     for(i=1;i<=m;i++)
 36         add(i,i+1,K,0);
 37     for(i=1;i<=n;i++)
 38         add(a[i].x,a[i].y,1,a[i].w);
 39     m++;
 40 }
 41 
 42 bool SPFA()
 43 {
 44     int head,tail,u,v;
 45     memset(use,0,sizeof(use));
 46     memset(d,0xff,sizeof(d));
 47     d[1]=0; f[1]=-1;
 48     use[1]=1;
 49     Q[head=tail=1]=1;
 50     while(head<=tail)
 51     {
 52         u=Q[head++];
 53         for(node *p=graph[u];p;p=p->next)
 54         {
 55             v=p->u;
 56             if(p->remain>0&&d[u]+p->cost>d[v])
 57             {
 58                 d[v]=d[u]+p->cost;
 59                 f[v]=u;
 60                 edge[v]=p;
 61                 if(!use[v])
 62                     use[v]=1, Q[++tail]=v;
 63             }
 64         }
 65         use[u]=0;
 66     }
 67     //for(int i=1;i<=m;i++)
 68     //cout<<i<<" "<<d[i]<<endl;
 69     return d[m]>-1;
 70 }
 71 int extend()
 72 {
 73     int i,delta=123456789,res=0;
 74     for(i=m;f[i]!=-1;i=f[i])
 75         delta=min(delta,edge[i]->remain);
 76     for(i=m;f[i]!=-1;i=f[i])
 77     {
 78         edge[i]->remain-=delta;
 79         edge[i]->inv->remain+=delta;
 80         res+=edge[i]->cost*delta;
 81         ///cout<<i<<" "<<delta<<" "<<edge[i]->remain<<endl;
 82     }
 83     //cout<<res<<endl;
 84     return res;
 85 }
 86 int main()
 87 {
 88     freopen("interval.in","r",stdin);
 89     freopen("interval.out","w",stdout);
 90     int i,j;
 91     scanf("%d",&T);
 92     while(T--)
 93     {
 94         top=0;
 95         memset(graph,0,sizeof(graph));
 96         scanf("%d%d",&n,&K);
 97         for(i=1;i<=n;i++)
 98         {
 99             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
100             b[i]=a[i].x; b[i+n]=a[i].y;
101         }
102         sort(b+1,b+2*n+1);
103         b[0]=-1;
104         j=0;
105         for(i=1;i<=2*n;i++)
106         {
107             if(b[i]!=b[i-1]) j++;
108             home[b[i]]=j;
109         }
110         m=j;
111         for(i=1;i<=n;i++)
112             a[i].x=home[a[i].x], a[i].y=home[a[i].y];
113         //for(i=1;i<=n;i++) cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
114         //cout<<endl;
115         build_graph();
116         int sum=0;
117         while(SPFA()) 
118             sum+=extend();
119         printf("%d\n",sum);
120     }
121     return 0;
122 }

北京集训 区间覆盖 费用流

北京集训区间覆盖费用流