网络流(最大费用最大流) ：POJ 3680 Intervals

Intervals

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 7218		Accepted: 3011

Description

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_i. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

Input

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers a_i, b_i, w_i(1 ≤ a_i < b_i ≤ 100,000, 1 ≤ w_i ≤ 100,000) describing the intervals.
There is a blank line before each test case.

Output

For each test case output the maximum total weights in a separate line.

Sample Input

4

3 1
1 2 2
2 3 4
3 4 8

3 1
1 3 2
2 3 4
3 4 8

3 1
1 100000 100000
1 2 3
100 200 300

3 2
1 100000 100000
1 150 301
100 200 300

Sample Output

14
12
100000
100301
　　
　　这题就是求最大区间K覆盖，最大费用最大流走起~~~

  1 #include <algorithm> 
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std;
  7 const int INF=233333333;
  8 const int maxn=2010,maxm=20010;
  9 int cnt,fir[maxn],nxt[maxm],to[maxm],cap[maxm],val[maxm],dis[maxn],path[maxn];
 10 struct data{
 11     int l,r,v;
 12     bool operator <(const data A)const{
 13         if(l!=A.l)
 14             return l<A.l;
 15         return r<A.r;     
 16     }
 17 }ar[maxn];
 18 
 19 struct data2{
 20     int a,pos;
 21     bool operator <(const data2 A)const{
 22         if(a!=A.a)
 23             return a<A.a;
 24         return pos<A.pos;     
 25     }
 26 }br[maxn];
 27 
 28 void addedge(int a,int b,int c,int v)
 29 {
 30     nxt[++cnt]=fir[a];to[cnt]=b;cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
 31 }
 32 int S,T;
 33 int Spfa()
 34 {
 35     queue<int>q;
 36     memset(dis,-1,sizeof(dis));
 37     q.push(S);dis[S]=0;
 38     while(!q.empty())
 39     {
 40         int node=q.front();q.pop();
 41         for(int i=fir[node];i;i=nxt[i])
 42             if(cap[i]&&dis[node]+val[i]>dis[to[i]]){
 43                 dis[to[i]]=val[i]+dis[node];
 44                 path[to[i]]=i;
 45                 q.push(to[i]);
 46             }
 47     }
 48     return dis[T]==-1?0:dis[T]; 
 49 }
 50 
 51 int Aug()
 52 {
 53     int p=T,f=INF;
 54     while(p!=S)
 55     {
 56         f=min(f,cap[path[p]]);
 57         p=to[path[p]^1];
 58     }
 59     p=T;
 60     while(p!=S)
 61     {
 62         cap[path[p]]-=f;
 63         cap[path[p]^1]+=f;
 64         p=to[path[p]^1];
 65     }
 66     return f;
 67 }
 68 
 69 int MCMF()
 70 {
 71     int ret=0,d;
 72     while(d=Spfa())
 73         ret+=Aug()*d;
 74     return ret;    
 75 }
 76 
 77 int cont;
 78 void Init()
 79 {
 80     cnt=1;cont=0;
 81     memset(fir,0,sizeof(fir));
 82 }
 83 
 84 int main()
 85 {
 86     int Q,n,k;
 87     scanf("%d",&Q);
 88     while(Q--)
 89     {
 90         Init();
 91         scanf("%d%d",&n,&k);    
 92         for(int i=1;i<=n;i++)
 93             scanf("%d%d%d",&ar[i].l,&ar[i].r,&ar[i].v);
 94         sort(ar+1,ar+n+1);
 95         for(int i=1;i<=n;i++){
 96             br[i*2-1].a=ar[i].l;br[i*2].a=ar[i].r;
 97             br[i*2-1].pos=br[i*2].pos=i;
 98         }
 99         sort(br+1,br+2*n+1);
100         for(int i=1;i<=n;i++)
101             ar[i].l=ar[i].r=0;
102         for(int i=1;i<=2*n;i++)
103         {
104             int p=br[i].pos;
105             if(!ar[p].l){
106                 ar[p].l=++cont;
107             }
108             else{
109                 ar[p].r=++cont;
110             }
111         }
112 
113         S=0;T=cont+1;
114         for(int i=0;i<cont+1;i++)
115             addedge(i,i+1,k,0),addedge(i+1,i,0,0); 
116         for(int i=1;i<=n;i++)
117             addedge(ar[i].l,ar[i].r,1,ar[i].v),addedge(ar[i].r,ar[i].l,0,-ar[i].v);
118         printf("%d
",MCMF());        
119     }
120 
121     return 0;
122 }

尽最大的努力，做最好的自己！