首页 > 代码库 > 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! 最小费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。