首页 > 代码库 > bzoj 1070 SCOI2007 修车
bzoj 1070 SCOI2007 修车
好久没写网络流了……
一开始以为是DP,没想出来,看题解发现是网络流。
构图蛮有意思的。
把维修人员拆成n个点,每个分点都与那n个点连边,费用为 c[i][j] * (1..n) 这是表示修了这个车后以后的人会增加这么些费用。
上代码:
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#define N 65#define M 15#define inf 0x7f7f7f7fusing namespace std;int n, m, S, T;int t[N][M], fa[N*M];int p[N*M], next[N*M*200], v[N*M*200], f[N*M*200], c[N*M*200], bnum = -1;int dis[N*M], vis[N*M];queue<int> q;void addbian(int x, int y, int fl, int co){ bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y; f[bnum] = fl; c[bnum] = co; bnum++; next[bnum] = p[y]; p[y] = bnum; v[bnum] = x; f[bnum] = 0; c[bnum] = -co;}bool bfs(){ for (int i = 1; i <= T; ++i) {dis[i] = inf; vis[i] = 0;} vis[S] = 1; q.push(S); dis[S] = 0; fa[S] = -1; while (!q.empty()) { int j = q.front(); q.pop(); int k = p[j]; while (k != -1) { if (f[k] && dis[v[k]] > dis[j] + c[k]) { fa[v[k]] = k; dis[v[k]] = dis[j] + c[k]; if (!vis[v[k]]) { vis[v[k]] = 1; q.push(v[k]); } } k = next[k]; } vis[j] = 0; } if (dis[T] == inf) return false; else return true;}void dinic(){ int ans = 0; while (bfs()) { int k = fa[T]; while (k != -1) { if (!f[k]) printf("now\n"); f[k] --; ans += c[k]; f[k^1] ++; k = fa[v[k^1]]; } } printf("%.2lf\n", (double)ans/(double)n);}int main(){ scanf("%d%d", &m, &n); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &t[i][j]); S = n*m+n+1; T = S+1; for (int i = 1; i <= T; ++i) p[i] = -1; for (int i = 1; i <= n*m; ++i) addbian(i, T, 1, 0); for (int i = 1; i <= n; ++i) addbian(S, n*m+i, 1, 0); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n*m; ++j) addbian(n*m+i, j, 1, t[i][(j-1)/n+1]*(j%n+1)); dinic(); return 0;}
bzoj 1070 SCOI2007 修车
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。