首页 > 代码库 > BZOJ1070 [SCOI2007]修车
BZOJ1070 [SCOI2007]修车
蒟蒻表示不太会。。。
后来才想明白怎么做：一个拆了很多很多点的网络流模型。（想法其实是先考虑一个修理师的情况，再考虑多个的情况）
把每个修理师拆成n个点，一辆车分别想着n个点连边，容量为1，费用为t * x 其中x = 1, 2, 3 ... n，表示在这之后修理车的人要总共等待t, t * 2, t * 3, t * 4...时间
然后跑一边最小费用最大流就可以了。
看上去非常对，就是这么做。。。搞定！
（p.s. 作死小剧场：我建图的时候建错了，然后查spfa死活找不出错来>.<）
1 /************************************************************** 2 Problem: 1070 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:608 ms 7 Memory:8744 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 16 const int inf = (int) 1e9;17 struct edges{18 int next, to, cost, f;19 } e[200000];20 21 int m, n, tot = 1, g[10000], first[10000], d[10000], q[200000];22 int a[1000][1000], s, t, ans;23 bool v[10000];24 25 inline void add_edge(int x, int y, int d, int c){26 e[++tot].next = first[x];27 first[x] = tot;28 e[tot].to = y;29 e[tot].f = d;30 e[tot].cost = c;31 }32 33 void add_Edges(int x, int y,int d, int c){34 add_edge(x, y, d, c);35 add_edge(y, x, 0, -c);36 }37 38 void build_graph(){39 for (int i = 1; i <= n; ++i)40 for (int j = 1; j <= m; ++j)41 for(int k = 1; k <= n; ++k)42 add_Edges(i, j * n + k, 1, a[i][j] * k);43 s = m * n + n + 1, t = m * n + n + 2;44 for (int i = 1; i <= n; ++i)45 add_Edges(s, i, 1, 0);46 for (int i = n + 1; i <= m * n + n; ++i)47 add_Edges(i, t, 1, 0);48 }49 50 inline int calc(){51 int flow = inf;52 for (int x = g[t]; x; x = g[e[x ^ 1].to])53 flow = min(flow, e[x].f);54 for (int x = g[t]; x; x = g[e[x ^ 1].to])55 e[x].f -= flow, e[x ^ 1].f += flow;56 return flow;57 }58 59 bool spfa(){60 for (int i = 1; i <= t; ++i)61 d[i] = inf;62 d[s] = 0, v[s] = 1;63 q[1] = s;64 int x, y;65 for(int l = 1, r = 1; l <= r; ++l){66 for (x = first[q[l]]; x; x = e[x].next){67 y = e[x].to;68 if (d[q[l]] + e[x].cost < d[y] && e[x].f){69 d[y] = d[q[l]] + e[x].cost;70 g[y] = x;71 if (!v[y])72 q[++r] = y, v[y] = 1;73 }74 }75 v[q[l]] = 0;76 }77 return d[t] != inf;78 }79 80 int main(){81 scanf("%d%d", &m, &n);82 for (int i = 1; i <= n; ++i)83 for (int j = 1; j <= m; ++j)84 scanf("%d", a[i] + j);85 86 build_graph();87 while (spfa())88 ans += calc() * d[t];89 printf("%.2lf\n", (double) ans / n);90 return 0;91 }
BZOJ1070 [SCOI2007]修车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。