Intervals
Time Limit: 5000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 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
43 11 2 22 3 43 4 83 11 3 22 3 43 4 83 11 100000 1000001 2 3100 200 3003 21 100000 1000001 150 301100 200 300
Sample Output
1412100000100301
Source
解题:离散化+费用流
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 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 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:"< < -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:"< <