首页 > 代码库 > _bzoj [SCOI2007]修车【最小费用最大流】
_bzoj [SCOI2007]修车【最小费用最大流】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1070
以后做网络流题目就是不能省内存。。。
#include <cstdio> #include <cstring> #include <algorithm> const int maxnd = 10100, maxe = 100005; int m, n, time[65][15], S, T; int head[maxnd], next[maxe], from[maxe], to[maxe], w[maxe], cap[maxe], flow[maxe], lb; int d[maxnd], p[maxnd], c[maxnd], que[maxnd], head_, tail, h; char inq[maxnd]; inline void ist(int aa, int ss, int ww, int ca) { to[lb] = ss; from[lb] = aa; next[lb] = head[aa]; head[aa] = lb; w[lb] = ww; cap[lb] = ca; ++lb; to[lb] = aa; from[lb] = ss; next[lb] = head[ss]; head[ss] = lb; w[lb] = -ww; cap[lb] = 0; ++lb; } inline bool spfa(int & co) { memset(d, 0x3c, sizeof d); memset(inq, 0, sizeof inq); head_ = tail = 0; que[tail++] = S; inq[S] = 1; d[S] = 0; c[S] = 2147483647; while (head_ != tail) { h = que[head_++]; inq[h] = 0; if (head_ == T + 3) { head_ = 0; } for (int j = head[h]; j != -1; j = next[j]) { if (flow[j] < cap[j] && d[to[j]] > d[h] + w[j]) { d[to[j]] = d[h] + w[j]; p[to[j]] = j; c[to[j]] = std::min(c[h], cap[j] - flow[j]); if (!inq[to[j]]) { inq[to[j]] = 1; que[tail++] = to[j]; if (tail == T + 3) { tail = 0; } } } } } if (d[T] == 0x3c3c3c3c) { return false; } co += d[T] * c[T]; for (int i = T; i != S; i = from[p[i]]) { flow[p[i]] += c[T]; flow[p[i] ^ 1] -= c[T]; } return true; } inline int mcmf(void) { int co = 0; while (spfa(co)); return co; } int main(void) { //freopen("in.txt", "r", stdin); memset(head, -1, sizeof head); memset(next, -1, sizeof next); scanf("%d%d", &m, &n); T = n * (m + 1) + 1; for (int i = 1; i <= n; ++i) { ist(S, i, 0, 1); for (int j = 1; j <= m; ++j) { scanf("%d", time[i] + j); } } for (int j = 1; j <= m; ++j) { for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { ist(i, j * n + k, time[i][j] * k, 1); } ist(j * n + k, T, 0, 1); } } printf("%.2f\n", (double)mcmf() / (double)n); return 0; }
_bzoj [SCOI2007]修车【最小费用最大流】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。