首页 > 代码库 > POJ 3762 The Bonus Salary! 最小费用最大流

POJ 3762 The Bonus Salary! 最小费用最大流


题意最后可以简化为

给出若干个区间,每个区间由左端点,右端点, 权值构成。

挑出若干个区间,使得权值和最大,但必须满足区间任意部分重叠次数不超过k


这题跟POJ3680一样一样的

构图是这样

先把这些区间都给hash了。 

hash完必然这些区间端点都落在1,2,3..., cnt   这些数中, cnt是hash完 不同数的个数

然后建边, 源点为S,汇点为T

S到1  建边  流量为k  费用为0

1到2,2到3,3到4....cnt-1到cnt   分别建边 流量为k 费用为0

cnt到T建边  流量为k  费用为0

然后对于每个区间[l,r] 费用为w的

建边 l 到 r  流量为1  费用为-w

这样你在图上一画

就能知道这样做的巧妙的。

那样互相之间不会重叠的区间,  一个流量就可以把他们都走完。

重叠了的区间自然要受到k这个限制。

每个区间走掉1个流量之后,会在右端点回归大部队


#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 4005
#define MAXM 1122222
#define INF 1000000001
using namespace std;
struct Interval {
    int a, b, w;
}p[2222];
int a[5555];
int nt, k;
int getnum(char a, char b) {
    return (a - '0') * 10 + (b - '0');
}
int gethash(char s[]) {
    int a = getnum(s[0], s[1]);
    int b = getnum(s[3], s[4]);
    int c = getnum(s[6], s[7]);
    return a * 3600 + b * 60 + c;
}
struct EDGE
{
    int v, cap, cost, next, re;    //  re记录逆边的下标。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
    e = ans = flow = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
    edge[e].v = v;
    edge[e].cap = cap;
    edge[e].cost = cost;
    edge[e].next = head[u];
    edge[e].re = e + 1;
    head[u] = e++;
    edge[e].v = u;
    edge[e].cap = 0;
    edge[e].cost = -cost;
    edge[e].next = head[v];
    edge[e].re = e - 1;
    head[v] = e++;
}
bool spfa()
{
    int i, h = 0, t = 1;
    for(i = 0; i <= n; i ++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[src] = 0;
    que[0] = src;
    vis[src] = true;
    while(t != h)
    {
        int u = que[h++];
        h %= n;
        vis[u] = false;
        for(i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    que[t++] = v;
                    t %= n;
                }
            }
        }
    }
    if(dis[des] == INF) return false;
    return true;
}
void end()
{
    int u, p, mi = INF;
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        mi = min(mi, edge[p].cap);
    }
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        edge[p].cap -= mi;
        edge[edge[p].re].cap += mi;
        ans += mi * edge[p].cost;     //  cost记录的为单位流量费用,必须得乘以流量。
    }
    flow += mi;
}

int main() {
    while(scanf("%d%d", &nt, &k) != EOF) {
        char s[11];
        int w;
        int cnt = 0;
        for(int i = 0; i < nt; i++) {
            scanf("%s", s);
            p[i].a = gethash(s);
            scanf("%s", s);
            p[i].b = gethash(s);
            scanf("%d", &w);
            p[i].w = w;
            a[cnt++] = p[i].a;
            a[cnt++] = p[i].b;
        }
        sort(a, a + cnt);
        cnt = unique(a, a + cnt) - a;
        for(int i = 0; i < nt; i++) {
            p[i].a = lower_bound(a, a + cnt, p[i].a) - a + 1;
            p[i].b = lower_bound(a, a + cnt, p[i].b) - a + 1;
        }
        init();
        src = http://www.mamicode.com/cnt + 1;>

POJ 3762 The Bonus Salary! 最小费用最大流