POJ 3680 Intervals

Intervals

Time Limit: 5000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3680
64-bit integer IO format: %lld Java class name: Main

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

Source

POJ Founder Monthly Contest – 2008.07.27

解题：离散化+费用流

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define INF 0x3f3f3f3f
 15 using namespace std;
 16 const int maxn = 1000;
 17 struct arc{
 18     int v,w,f,next;
 19     arc(int x = 0,int y = 0,int z = 0,int nxt = 0){
 20         v = x;
 21         w = y;
 22         f = z;
 23         next = nxt;
 24     }
 25 };
 26 arc e[10000];
 27 int head[maxn],d[maxn],p[maxn],tot;
 28 int n,k,S,T,lisan[maxn],cnt,x[maxn],y[maxn],sc[maxn];
 29 bool in[maxn];
 30 queue<int>q;
 31 void add(int u,int v,int w,int f){
 32     e[tot] = arc(v,w,f,head[u]);
 33     head[u] = tot++;
 34     e[tot] = arc(u,-w,0,head[v]);
 35     head[v] = tot++;
 36 }
 37 bool spfa(){
 38     for(int i = 0; i <= T; i++){
 39         d[i] = INF;
 40         in[i] = false;
 41         p[i] = -1;
 42     }
 43     while(!q.empty()) q.pop();
 44     d[S] = 0;
 45     in[S] = true;
 46     q.push(S);
 47     while(!q.empty()){
 48         int u = q.front();
 49         q.pop();
 50         in[u] = false;
 51         for(int i = head[u]; ~i; i = e[i].next){
 52             if(e[i].f > 0 && d[e[i].v] > d[u] + e[i].w){
 53                 d[e[i].v] = d[u] + e[i].w;
 54                 //cout<<"end:"<<e[i].v<<endl;
 55                 p[e[i].v] = i;
 56                 if(!in[e[i].v]){
 57                     in[e[i].v] = true;
 58                     q.push(e[i].v);
 59                 }
 60             }
 61         }
 62     }
 63     return p[T] > -1;
 64 }
 65 int solve(){
 66     int tmp = 0,minV;
 67     while(spfa()){
 68         minV = INF;
 69         for(int i = p[T]; ~i; i = p[e[i^1].v])
 70             minV = min(minV,e[i].f);
 71         for(int i = p[T]; ~i; i = p[e[i^1].v]){
 72             tmp += minV*e[i].w;
 73             e[i].f -= minV;
 74             e[i^1].f += minV;
 75         }
 76         //cout<<"tmp:"<<tmp<<endl;
 77     }
 78     return tmp;
 79 }
 80 int main(){
 81     int t;
 82     scanf("%d",&t);
 83     while(t--){
 84         scanf("%d %d",&n,&k);
 85         memset(head,-1,sizeof(head));
 86         cnt = tot = 0;
 87         //cout<<"n:"<<n<<endl;
 88         for(int i = 0; i < n; i++){
 89             scanf("%d %d %d",x+i,y+i,sc+i);
 90             lisan[cnt++] = x[i];
 91             lisan[cnt++] = y[i];
 92         }
 93         sort(lisan,lisan+cnt);
 94         int cnt1 = 1;
 95         for(int i = 1; i < cnt; i++)
 96             if(lisan[cnt1-1] != lisan[i]) lisan[cnt1++] = lisan[i];
 97         cnt = cnt1;
 98         S = 0;
 99         T = cnt;
100         //cout<<"n:"<<n<<endl;
101         for(int i = 0; i < n; i++){
102             int tx = lower_bound(lisan,lisan+cnt,x[i])-lisan;
103             int ty = lower_bound(lisan,lisan+cnt,y[i])-lisan;
104             //cout<<tx<<" "<<ty<<" ---"<<endl;
105             add(tx,ty,-sc[i],1);
106             add(tx,ty,0,k);
107         }
108         for(int i = 0; i < cnt; i++) add(i,i+1,0,k);
109         printf("%d
",-solve());
110     }
111     return 0;
112 }

View Code