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

时间：2022-09-09 16:24:12
Intervals
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 7218   Accepted: 3011

Description

You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi. 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 ai, bi, wi(1 ≤ ai < bi ≤ 100,000, 1 ≤ wi ≤ 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\n",MCMF());        
119     }
120 
121     return 0;
122 }

 

标签：

相关文章