首页 > 代码库 > bzoj1221
bzoj1221
费用流
和3280很像,先建出上下界模型,然后转为普通费用流模型
s->1 flow=inf, c = f
s->i+n flow=x,c=0;
i->t,flow=x,c=0
i->i+1 flow=inf, c=0;
i+n->i+n+1,flow=inf,c=0
i->i+a+1,i->i+b+1,flow=inf,c=fa/fb
i表示到第i天干净的抹布
i+n表示第i天不干净的抹布
i->i+n上下界都为x,对于上下界的处理只需要连3条边就行了,对于边(u,v),从s->v,flow=下界,c=(u,v)的费用,u->t,flow=下界,c=0,u->v,flow=上界-下界,c=(u,v)的费用
#include<bits/stdc++.h> using namespace std; const int N = 2010, inf = 1 << 29; struct edge { int nxt, to, f, c; } e[N * 40]; int n, m, source, sink, cnt = 1, a, b, f, fa, fb; int head[N], d[N], pree[N], prev[N], vis[N]; void link(int u, int v, int f, int c) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].f = f; e[cnt].c = c; } void insert(int u, int v, int f, int c) { link(u, v, f, c); link(v, u, 0, -c); } bool spfa() { queue<int> q; q.push(source); memset(d, -1, sizeof(d)); d[source] = 0; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i; i = e[i].nxt) if(e[i].f && (d[e[i].to] > d[u] + e[i].c || d[e[i].to] == -1)) { d[e[i].to] = d[u] + e[i].c; pree[e[i].to] = i; prev[e[i].to] = u; if(vis[e[i].to] == 0) { vis[e[i].to] = 1; q.push(e[i].to); } } } return d[sink] != -1; } inline int Edmonds_Karp() { int ret = 0; while(spfa()) { int now = sink, delta = inf; while(now != source) { delta = min(delta, e[pree[now]].f); now = prev[now]; } now = sink; while(now != source) { e[pree[now]].f -= delta; e[pree[now] ^ 1].f += delta; now = prev[now]; } ret += delta * d[sink]; } return ret; } int main() { scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb); sink = 2 * n + 1; insert(source, 1, inf, f); for(int i = 1; i <= n; ++i) { int x; scanf("%d", &x); insert(source, i + n, x, 0); insert(i, sink, x, 0); if(i < n) { insert(i, i + 1, inf, 0); insert(i + n, i + n + 1, inf, 0); } if(i + a + 1 <= n) insert(i + n, i + a + 1, inf, fa); if(i + b + 1 <= n) insert(i + n, i + b + 1, inf, fb); } printf("%d\n", Edmonds_Karp()); return 0; }
bzoj1221
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。