注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【最长k可重区间集问题】  

2014-02-14 15:37:01|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  题目大意就是在N个区间中选出一些区间使他们每一个重叠的部分不超过K个区间,要求满足这样条件的区间集合的长度最长。
   首先庆贺从WC2014回来...(被虐的很惨....),不过也得到了LRJ大神在他写的白书上的签名=w=。
   接下来是题意,区间K重,显然我们把区间离散化啥的最好,然后由于不能超过K个区间,也就是可以把选择的容量设为K,然后我们开始建图。怎么建呢....首先咱们YY了下容量为K,所以我们的流就是决定选不选某个区间的,假设对于某个流它经过了某个区间,那么这个区间就要被选,为此咱们可以加一个费用,这样就是跑费用流...但是问题是怎么把区间建成图,咱们已经离散化了,我们对于离散化的结果从小到大连边,假设有一个方案是区间[i,j]到区间[u,v]我们连一条容量为无穷大的费用为0的边,然后源点对于起始点连容量为K,费用为0的边,汇点也一样,然后对于每条边的末端都连汇一条边,源连起点,跑费用流即可。
    然后发现咱的YY就是丧心病狂的乱...所以直接上代码吧....
   (这里直接从源点流出K流量的流,然后就不用加限制了...)
   这里又一次傻了的忘了最大费用的初始化了...
   然后就是在WC没电脑码代码...结果现在喜欢用容量表示费用,费用表示容量.....
=========================================================

program flow21;
const maxn=10000;
type
  edges=record
  u,v,w,c,pre:longint;
  end;

var
  e:array[0..maxn]of edges;
  last:array[0..maxn]of longint;
  v:array[0..maxn]of boolean;
  que,low,pre,d,x,y,w:array[0..maxn]of longint;
  num,tot,n,limit,cost:longint;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

procedure addedge(u,v,w,c:longint);
begin
  inc(tot);
  e[tot].u:=u;
  e[tot].v:=v;
  e[tot].c:=c;
  e[tot].w:=w;
  e[tot].pre:=last[u];
  last[u]:=tot;
  inc(tot);
  e[tot].u:=v;
  e[tot].v:=u;
  e[tot].c:=-c;
  e[tot].w:=0;
  e[tot].pre:=last[v];
  last[v]:=tot;
end;

function spfa(s,t:longint):boolean;
var u,l,r,tmp,aug:longint;
begin
  fillchar(v,sizeof(v),false);
  fillchar(que,sizeof(que),0);
  fillchar(low,sizeof(low),0);
  fillchar(d,sizeof(d),254);
  d[s]:=0;v[s]:=true;
  l:=0;r:=1;que[l]:=s;
  low[s]:=maxlongint;
  low[t]:=low[s];
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (e[tmp].w>0)and(d[e[tmp].v]<d[u]+e[tmp].c) then
         begin
           d[e[tmp].v]:=d[u]+e[tmp].c;
           pre[e[tmp].v]:=tmp;
           low[e[tmp].v]:=min(low[u],e[tmp].w);
           if not v[e[tmp].v] then
            begin
              que[r]:=e[tmp].v;
              r:=(r+1)mod maxn;
              v[e[tmp].v]:=true;
            end;
         end;
        tmp:=e[tmp].pre;
      end;
     v[u]:=false;
     l:=(l+1)mod maxn;
   end;
  if low[t]=maxlongint then exit(false);
  u:=t;aug:=low[t];
  cost:=cost+low[t]*d[t];
  while u<>s do
   begin
     dec(e[pre[u]].w,aug);
     inc(e[pre[u] xor 1].w,aug);
     u:=e[pre[u]].u;
   end;
  exit(true);
end;

procedure qsort(l,r:longint);
var i,j,u,v:longint;
begin
  i:=l;j:=r;
  u:=w[(l+r)shr 1];
  repeat
    while w[i]<u do inc(i);
    while w[j]>u do dec(j);
    if i<=j then
     begin
       v:=w[i];w[i]:=w[j];w[j]:=v;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure prepare;
var i,j:longint;
begin
  j:=1;
  qsort(1,n shl 1);
  for i:=2 to n shl 1 do
   if w[i]<>w[j] then
    begin
      inc(j);
      w[j]:=w[i];
    end;
  num:=j;
end;

function find(a:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=num;
  while l<>r do
   begin
     mid:=(l+r)shr 1;
     if w[mid]=a then exit(mid);
     if w[mid]>a then r:=mid-1
                 else l:=mid+1;
   end;
  exit(l);
end;

procedure init;
var i:longint;
begin
  read(n,limit);
  for i:=1 to n do
   begin
     read(x[i],y[i]);
     w[i shl 1-1]:=x[i];
     w[i shl 1]:=y[i];
   end;
  prepare;
  fillchar(last,sizeof(last),255);
  tot:=-1;
  for i:=1 to num-1 do
   addedge(i,i+1,maxlongint shr 1,0);
  addedge(0,1,limit,0);
  addedge(num,num+1,limit,0);
  for i:=1 to n do
   addedge(find(x[i]),find(y[i]),1,y[i]-x[i]);
  cost:=0;
  while spfa(0,num+1) do;
  writeln(cost);
end;

begin
  init;
end.


  评论这张
 
阅读(42)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018