首页 > 代码库 > [BZOJ 1070] [SCOI2007] 修车 【费用流】
[BZOJ 1070] [SCOI2007] 修车 【费用流】
题目链接：BZOJ - 1070
题目分析
首先想到拆点，把每个技术人员拆成 n 个点，从某个技术人员拆出的第 i 个点，向某辆车连边，表示这是这个技术人员修的倒数第 i 辆车。那么这一次修车对整个答案的贡献就是，i * Time[j][k]。 j 是车的编号，k 是技术人员编号。因为这辆车以及之后这个人要修的车的等待时间都增加了 Time[j][k]， 所以包括这辆车在内一共有 i 辆车的等待时间加上了这次修车的时间。这样倒着考虑就可以用边的费用很简便的表示修车使所有人增加的时间了。从 S 到所有技术人员拆出的所有点连边，容量 1 ， 费用 0 ；从每辆车向 T 连边，容量 1 ，费用 0 。
最后跑一边最小费用最大流就是所有车等待时间的和。
代码
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>using namespace std;const int MaxN = 1000 + 5, MaxM = 100000 + 5, INF = 999999999;int n, m, S, T, Ans;int Time[60 + 5][9 + 5], d[MaxN];bool Used[MaxN];queue<int> Q;inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;} struct Edge { int u, v, w, Cost; Edge *Next, *Other;} E[MaxM], *P = E, *Point[MaxN], *Pre[MaxN]; inline void AddEdge(int x, int y, int z, int Ct) { Edge *Q = ++P; ++P; P -> u = x; P -> v = y; P -> w = z; P -> Cost = Ct; P -> Next = Point[x]; Point[x] = P; P -> Other = Q; Q -> u = y; Q -> v = x; Q -> w = 0; Q -> Cost = -Ct; Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P; }bool Found() { memset(d, 0x7f, sizeof(d)); memset(Used, 0, sizeof(Used)); d[S] = 0; Used[S] = true; Q.push(S); while (!Q.empty()) { int x = Q.front(); Used[x] = false; Q.pop(); for (Edge *j = Point[x]; j; j = j -> Next) { if (j -> w && d[j -> v] > d[x] + j -> Cost) { d[j -> v] = d[x] + j -> Cost; Pre[j -> v] = j; if (!Used[j -> v]) { Used[j -> v] = true; Q.push(j -> v); } } } } if (d[T] < INF) return true; return false;}void Augment() { int Flow; Flow = INF; for (Edge *j = Pre[T]; j; j = Pre[j -> u]) Flow = gmin(Flow, j -> w); for (Edge *j = Pre[T]; j; j = Pre[j -> u]) { j -> w -= Flow; j -> Other -> w += Flow; } Ans += Flow * d[T];}int main() { scanf("%d%d", &m, &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &Time[i][j]); } } S = n * m + n + 1; T = S + 1; for (int i = 1; i <= n * m; ++i) AddEdge(S, i, 1, 0); for (int i = n * m + 1; i <= n * m + n; ++i) AddEdge(i, T, 1, 0); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { for (int k = 1; k <= n; ++k) { AddEdge((i - 1) * n + j, n * m + k, 1, j * Time[k][i]); } } } Ans = 0; while (Found()) Augment(); printf("%.2lf\n", (double)Ans / (double)n); return 0; }
[BZOJ 1070] [SCOI2007] 修车 【费用流】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。