【POJ3680】Intervals（费用流）

题意：有n条线段，每条有起点，终点和一个权值

要求选取一些线段，使它们的权值和最大，并且使每一个点被覆盖不超过k次

1 ≤ K ≤ N ≤ 200

1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000

思路：RYZ作业

费用流（经典？）模型之一

离散化后对于线段(a[i],b[i],w[i])，从a[i]到b[i]连容量为1,费用为w[i]的边

(i,i+1)之间都连容量为K，费用为0的边，以达到限制max<=k的效果

S——>1和N——>T之间都连容量为K，费用为0的边

跑最大费用最大流

  1 var head,vet,next,len1,len2,a,b,c,d,fan:array[1..100000]of longint;
  2     inq:array[1..30000]of boolean;
  3     q:array[0..30000]of longint;
  4     pre:array[1..30000,1..2]of longint;
  5     dis:array[1..30000]of longint;
  6     n,m,k,up,i,tot,ans,s,source,src,cas,v,x,y:longint;
  7 
  8 procedure swap(var x,y:longint);
  9 var t:longint;
 10 begin
 11  t:=x; x:=y; y:=t;
 12 end;
 13 
 14 procedure qsort(l,r:longint);
 15 var i,j,mid:longint;
 16 begin
 17  i:=l; j:=r; mid:=d[(l+r)>>1];
 18  repeat
 19   while mid>d[i] do inc(i);
 20   while mid<d[j] do dec(j);
 21   if i<=j then
 22   begin
 23    swap(d[i],d[j]);
 24    inc(i); dec(j);
 25   end;
 26  until i>j;
 27  if l<j then qsort(l,j);
 28  if i<r then qsort(i,r);
 29 end;
 30 
 31 function min(x,y:longint):longint;
 32 begin
 33  if x<y then exit(x);
 34  exit(y);
 35 end;
 36 
 37 function hash(x:longint):longint;
 38 var l,r,mid:longint;
 39 begin
 40  l:=1; r:=up;
 41  while l<=r do
 42  begin
 43   mid:=(l+r)>>1;
 44   if d[mid]=x then exit(mid);
 45   if d[mid]<x then l:=mid+1
 46    else r:=mid-1;
 47  end;
 48 end;
 49 
 50 procedure add(a,b,c,d:longint);
 51 begin
 52  inc(tot);
 53  next[tot]:=head[a];
 54  vet[tot]:=b;
 55  len1[tot]:=c;
 56  len2[tot]:=d;
 57  head[a]:=tot;
 58 
 59  inc(tot);
 60  next[tot]:=head[b];
 61  vet[tot]:=a;
 62  len1[tot]:=0;
 63  len2[tot]:=-d;
 64  head[b]:=tot;
 65 end;
 66 
 67 function spfa:boolean;
 68 var u,e,v,i,top:longint;
 69 begin
 70  for i:=1 to s do
 71  begin
 72   dis[i]:=-(maxlongint>>1);
 73   inq[i]:=false;
 74  end;
 75  top:=1; q[1]:=source; dis[source]:=0; inq[source]:=true;
 76  while top>0 do
 77  begin
 78   u:=q[top]; dec(top); inq[u]:=false;
 79   e:=head[u];
 80   while e<>0 do
 81   begin
 82    v:=vet[e];
 83    if (len1[e]>0)and(dis[u]+len2[e]>dis[v]) then
 84    begin
 85     dis[v]:=dis[u]+len2[e];
 86     pre[v,1]:=u;
 87     pre[v,2]:=e;
 88     if not inq[v] then
 89     begin
 90      inc(top); q[top]:=v; inq[v]:=true;
 91     end;
 92    end;
 93    e:=next[e];
 94   end;
 95  end;
 96  if dis[src]=-(maxlongint>>1) then exit(false);
 97  exit(true);
 98 end;
 99 
100 procedure mcf;
101 var k,e,t:longint;
102 begin
103  k:=src; t:=maxlongint;
104  while k<>source do
105  begin
106   t:=min(t,len1[pre[k,2]]);
107   k:=pre[k,1];
108  end;
109  k:=src;
110  while k<>source do
111  begin
112   e:=pre[k,2];
113   len1[e]:=len1[e]-t;
114   len1[fan[e]]:=len1[fan[e]]+t;
115   ans:=ans+t*len2[e];
116   k:=pre[k,1];
117  end;
118 end;
119 
120 begin
121  assign(input,'poj3680.in'); reset(input);
122  assign(output,'poj3680.out'); rewrite(output);
123  readln(cas);
124  for i:=1 to 100000 do
125   if i and 1=1 then fan[i]:=i+1
126    else fan[i]:=i-1;
127  for v:=1 to cas do
128  begin
129   for i:=1 to s do head[i]:=0;
130   s:=0; tot:=0; ans:=0;
131   //fillchar(head,sizeof(head),0);
132   read(n,k); m:=0;
133   for i:=1 to n do
134   begin
135    read(a[i],b[i],c[i]);
136    inc(m); d[m]:=a[i];
137    inc(m); d[m]:=b[i];
138   end;
139   qsort(1,m);
140   up:=1;
141   for i:=2 to m do
142    if d[i]<>d[up] then begin inc(up); d[up]:=d[i]; end;
143   for i:=1 to n do
144   begin
145    x:=hash(a[i]); y:=hash(b[i]);
146    add(x,y,1,c[i]);
147   end;
148   source:=up+1; src:=up+2; s:=up+2;
149   add(source,1,k,0);
150   add(up,src,k,0);
151   for i:=1 to up-1 do add(i,i+1,k,0);
152   while spfa do mcf;
153   writeln(ans);
154  end;
155  close(input);
156  close(output);
157 end.