首页 > 代码库 > BZOJ1221 [HNOI2001] 软件开发
BZOJ1221 [HNOI2001] 软件开发
这题面和软件有个。。。毛关系啊！！！
建图什么的还是挺好想的。。。懒得写了，copy from AutSky_JadeK:"
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m+1(i+m+1<=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n+1(i+n+1<=N)连一条容量为无穷大，费用为s的有向边。
求网络最小费用最大流，费用流值就是要求的最小总花费。"
补充：S、T分别表示毛巾来源和公司
1 /************************************************************** 2 Problem: 1221 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1736 ms 7 Memory:1780 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 const int N = 2005;15 const int M = N * 30;16 const int inf = (int) 1e9;17 18 struct edges {19 int next, to, f, cost;20 edges() {}21 edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {}22 } e[M];23 24 int n, S, T;25 int first[N], tot = 1;26 int d[N], g[N], q[N];27 bool v[N];28 29 inline void Add_Edges(int x, int y, int f, int c) {30 e[++tot] = edges(first[x], y, f, c), first[x] = tot;31 e[++tot] = edges(first[y], x, 0, -c), first[y] = tot;32 }33 34 inline int calc() {35 int flow = inf, x;36 for (x = g[T]; x; x = g[e[x ^ 1].to])37 flow = min(flow, e[x].f);38 for (x = g[T]; x; x = g[e[x ^ 1].to])39 e[x].f -= flow, e[x ^ 1].f += flow;40 return flow;41 }42 43 bool spfa() {44 int x, y, l, r;45 for (x = 1; x <= T; ++x)46 d[x] = inf;47 d[S] = 0, v[S] = 1, q[0] = S;48 for(l = r = 0; l != (r + 1) % N; ++l %= N) {49 for (x = first[q[l]]; x; x = e[x].next)50 if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) {51 d[y] = d[q[l]] + e[x].cost, g[y] = x;52 if (!v[y])53 q[++r %= N] = y, v[y] = 1;54 }55 v[q[l]] = 0;56 }57 return d[T] != inf;58 }59 60 inline int work() {61 int res = 0;62 while (spfa())63 res += calc() * d[T];64 return res;65 }66 67 int main() {68 int i, a, b,f, fa, fb, x;69 scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb);70 S = n * 2 + 1, T = S + 1;71 for (i = 1; i <= n; ++i) {72 if (i + 1 <= n) Add_Edges(i, i + 1, inf, 0);73 if (i + a + 1 <= n) Add_Edges(i, n + i + a + 1, inf, fa);74 if (i + b + 1 <= n) Add_Edges(i, n + i + b + 1, inf, fb);75 Add_Edges(S, n + i, inf, f);76 scanf("%d", &x);77 Add_Edges(S, i, x, 0);78 Add_Edges(n + i, T, x, 0);79 }80 printf("%d\n", work());81 }
（p.s. 那个、、、rank 1的0ms是怎么做到的←_←）
BZOJ1221 [HNOI2001] 软件开发
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。