首页 > 代码库 > POJ 3680 Intervals 离散 + 费用流

POJ 3680 Intervals 离散 + 费用流

2024-07-06 10:29:01   226人阅读

Intervals
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 6246   Accepted: 2542

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

Source

POJ Founder Monthly Contest – 2008.07.27, windy7926778

 

题目大意：给你 n 个开区间，区间有权值，问如何选择区间使得每个点上覆盖的区间数不超过 k 个的前提下获得的最大权值和。

题目分析：做之前正好看过大白鼠的方法，所以过的没压力。首先，先对区间的端点进行离散化，之后对每个区间的左端点u和右端点v建边（u，v，1，-w），再对每个坐标点 i 建边（i，i + 1，k，0），设离散后最大的点的坐标为x，建立源汇点s = 0， t = x + 1，建边（x，t，1，0）。跑一次最小费用最大流，结果即花费的相反数。

 

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define REP(i, n) for(int i = 0; i < n; ++i)
#define MS0(X) memset(X,  0, sizeof X)
#define MS1(X) memset(X, -1, sizeof X)
using namespace std;
const int maxE = 3000000;
const int maxN = 500;
const int maxM = 55;
const int oo = 0x3f3f3f3f;
struct Edge{
    int v, c, w, n;
};
Edge edge[maxE];
int adj[maxN], l;
int d[maxN], cur[maxN], Minflow;
int inq[maxN], Q[maxE], head, tail;
int cost, flow, s, t;
int n, m, cnt;
struct Node{
    int l, r, w;
}a[maxN];
int b[maxN];
void addedge(int u, int v, int c, int w){
    edge[l].v = v; edge[l].c = c; edge[l].w =  w; edge[l].n = adj[u]; adj[u] = l++;
    edge[l].v = u; edge[l].c = 0; edge[l].w = -w; edge[l].n = adj[v]; adj[v] = l++;
}
int SPFA(){
    memset(d, oo, sizeof d);
    memset(inq, 0, sizeof inq);
    head = tail = 0;
    d[s] = 0;
    Minflow = oo;
    cur[s] = -1;
    Q[tail++] = s;
    while(head != tail){
        int u =  Q[head++];
        inq[u] = 0;
        for(int i = adj[u]; ~i; i = edge[i].n){
            int v = edge[i].v;
            if(edge[i].c && d[v] > d[u] + edge[i].w){
                d[v] = d[u] + edge[i].w;
                cur[v] = i;
                Minflow = min(edge[i].c, Minflow);
                if(!inq[v]){
                    inq[v] = 1;
                    Q[tail++] = v;
                }
            }
        }
    }
    if(d[t] == oo) return 0;
    flow += Minflow;
    cost += Minflow * d[t];
    for(int i = cur[t]; ~i; i = cur[edge[i ^ 1].v]){
        edge[i].c -= Minflow;
        edge[i ^ 1].c += Minflow;
    }
    return 1;
}
int MCMF(){
    flow = cost = 0;
    while(SPFA());
    return cost;
}
void work(){
    MS1(adj);
    l = 0;
    scanf("%d%d", &n, &m);
    REP(i, n) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
    cnt = 0;
    REP(i, n){
        b[cnt++] = a[i].l;
        b[cnt++] = a[i].r;
    }
    sort(b, b + cnt);
    int cnt1 = 0;
    REP(i, cnt) if(i && b[i] != b[cnt1]) b[++cnt1] = b[i];
    cnt = ++cnt1;
    //不会离散化就这么蠢蠢的离散好了QvQ
    REP(i, n) REP(j, cnt) if(a[i].l == b[j]){
        a[i].l = j;
        break;
    }
    REP(i, n) REP(j, cnt) if(a[i].r == b[j]){
        a[i].r = j;
        break;
    }
    s = 0; t = cnt;
    REP(i, n) addedge(a[i].l, a[i].r, 1, -a[i].w);
    REP(i, cnt) addedge(i, i + 1, m, 0);
    printf("%d\n", -MCMF());
}
int main(){
    int T, cas;
    for(scanf("%d", &T), cas = 1; cas <= T; ++cas) work();
    return 0;
}
POJ 3680

 


联系
我们