POJ 3680

一道思想比较神奇的网络流....

题意：给定一些带权的左闭右开区间，求一种选择区间的方案满足每个点被覆盖不超过k次并使权值和最大。

一开始的思路是将区间离散化后建立一个二分图模型，一边是点，一边是区间，然后把每个点和覆盖它的区间连边，但是这样是没法做的，因为区间的权值在点上，而且流量也没法弄

我们考虑建立这样一个模型，将所有的点串连，然后对于一个区间(l,r]，我们在点l和点r处连一条边，容量为1，费用为区间权值，对于相邻两点，我们连容量为INF，费用为0的边，然后S向1号点连边，容量为K，费用为0，n号点向T连边，容量为K，费用为0，跑一遍最大费用最大流即可。

为什么这样是对的，我们考虑对于每次增广，一定是选了若干个互不相交的区间，而且这些区间一定和我们之前增广的区间有交，这样我们连续增广K次，每个点被覆盖一定不超过K次

感觉自己网络流只会二分图建图....这方面还有待加强..

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define maxn 3005
  6 const int INF=1000000000;
  7 int pre[maxn],last[maxn],other[maxn],cap[maxn],cost[maxn];
  8 int que[maxn+4],dis[maxn],next[maxn];
  9 int C,n,m,k,b[maxn],l,S,T,ans;
 10 bool vis[maxn];
 11 struct Line
 12 {
 13     int l,r,w;
 14 }a[maxn];
 15 
 16 void init(void) 
 17 {
 18     memset(last,0,sizeof last);
 19     n=0;ans=0;l=1;
 20     scanf("%d%d",&m,&k);
 21     for (int i=1;i<=m;i++) 
 22     {
 23         scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
 24         b[++n]=a[i].l;
 25         b[++n]=a[i].r;
 26     }
 27     sort(b+1,b+n+1);
 28     n=unique(b+1,b+n+1)-b-1;
 29     for (int i=1;i<=m;i++) 
 30         a[i].l=lower_bound(b+1,b+n+1,a[i].l)-b,
 31         a[i].r=lower_bound(b+1,b+n+1,a[i].r)-b;
 32 }
 33 
 34 void connect(int x,int y,int z,int w)
 35 {
 36     l++;
 37     pre[l]=last[x];
 38     last[x]=l;
 39     other[l]=y;
 40     cap[l]=z;
 41     cost[l]=w;
 42     swap(x,y);
 43     l++;
 44     pre[l]=last[x];
 45     last[x]=l;
 46     other[l]=y;
 47     cap[l]=0;
 48     cost[l]=-w;
 49 }
 50 
 51 bool spfa(void) 
 52 {
 53     memset(dis,-1,sizeof dis);
 54     memset(next,0,sizeof next);
 55     que[1]=S;dis[S]=0;
 56     int h=0,t=1;
 57     while (h!=t) 
 58     {
 59         h=h%maxn+1;
 60         int u=que[h];vis[u]=0;
 61         for (int p=last[u];p;p=pre[p])
 62         {
 63             int v=other[p];
 64             if (cap[p]==0) continue;
 65             if (dis[v]<dis[u]+cost[p]) 
 66             {
 67                 dis[v]=dis[u]+cost[p];
 68                 next[v]=p;
 69                 if (vis[v]) continue;
 70                 t=t%maxn+1;
 71                 que[t]=v;
 72                 vis[v]=1;
 73             }
 74         }
 75     }
 76     return dis[T]>0;
 77 }
 78 
 79 void MCMF(void) 
 80 {
 81     while (spfa()) 
 82     {
 83         int flow=INF;
 84         for (int p=next[T];p;p=next[other[p^1]]) flow=min(flow,cap[p]);
 85         for (int p=next[T];p;p=next[other[p^1]]) 
 86             cap[p]-=flow,cap[p^1]+=flow;
 87         ans+=flow*dis[T];
 88     }
 89 }
 90 
 91 int main()
 92 {
 93     scanf("%d",&C);
 94     while (C--) 
 95     {
 96         init();
 97         for (int i=1;i<n;i++)
 98             connect(i,i+1,INF,0);
 99         S=n+1;T=n+2;
100         connect(S,1,k,0);
101         connect(n,T,k,0);
102         for (int i=1;i<=m;i++) connect(a[i].l,a[i].r,1,a[i].w);
103         MCMF();
104         printf("%d\n",ans);
105     }
106     return 0;
107 }