首页 > 代码库 > UVA 1317 - Concert Hall Scheduling(网络流)
UVA 1317 - Concert Hall Scheduling(网络流)
UVA 1317 - Concert Hall Scheduling
题目链接
题意:现在有两个音乐厅,有一些人要租用,每次租一个区间的时间,给w钱,要求一个租的方案使得总收入最大,问总收入
思路:区间k覆盖问题,一个左闭右开区间可以建一条边,容量为1,代价为-w(因为要求最大),然后区间每个[i, i + 1]建一条边,容量2,代价0,然后跑一下费用流即可
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXNODE = 400; const int MAXEDGE = 5005 * 4; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type cap, flow, cost; Edge() {} Edge(int u, int v, Type cap, Type flow, Type cost) { this->u = u; this->v = v; this->cap = cap; this->flow = flow; this->cost = cost; } }; struct MCFC { int n, m, s, t; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; int inq[MAXNODE]; Type d[MAXNODE]; int p[MAXNODE]; Type a[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type cap, Type cost) { edges[m] = Edge(u, v, cap, 0, cost); next[m] = first[u]; first[u] = m++; edges[m] = Edge(v, u, 0, 0, -cost); next[m] = first[v]; first[v] = m++; } bool bellmanford(int s, int t, Type &flow, Type &cost) { for (int i = 0; i < n; i++) d[i] = INF; memset(inq, false, sizeof(inq)); d[s] = 0; inq[s] = true; p[s] = s; a[s] = INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (e.cap > e.flow && d[e.v] > d[u] + e.cost) { d[e.v] = d[u] + e.cost; p[e.v] = i; a[e.v] = min(a[u], e.cap - e.flow); if (!inq[e.v]) {Q.push(e.v); inq[e.v] = true;} } } } if (d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; int u = t; while (u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].u; } return true; } Type Mincost(int s, int t) { Type flow = 0, cost = 0; while (bellmanford(s, t, flow, cost)); return cost; } } gao; const int N = 1005; int n; int main() { while (~scanf("%d", &n) && n) { gao.init(367); for (int i = 0; i < 366; i++) gao.add_Edge(i, i + 1, 2, 0); int u, v, w; while (n--) { scanf("%d%d%d", &u, &v, &w); gao.add_Edge(u, v + 1, 1, -w); } printf("%d\n", -gao.Mincost(0, 366)); } return 0; }
UVA 1317 - Concert Hall Scheduling(网络流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。