首页 > 代码库 > 费用流做题记录
费用流做题记录
BZOJ1221:http://www.lydsy.com/JudgeOnline/problem.php?id=1221
trick:将每天用完的,和要用的分来开处理,避免花费的重叠计算,也就是拆点
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 4e5+10, M = 1e3+20, mod = 1e9+7,inf = 2e7;int na[N],ans,ans1,S,T,head[N],cnt = 1,n,dis[N],q[N],inq[N],from[N],f,fA,fB;struct { int from,to,next,c,v;}e[N * 2];void ins(int u,int v,int w,int c) { cnt++; e[cnt].from = u; e[cnt].to = v; e[cnt].v = w; e[cnt].c = c; e[cnt].next = head[u]; head[u] = cnt;}void insert(int u,int v,int w,int c) { ins(u,v,w,c);ins(v,u,0,-c);}int spfa() { for(int i = 0; i <= T; ++i) dis[i] = inf; int t = 0,w = 1; dis[S] = q[S] = S; inq[S] = 1; while(t!=w) { int now = q[t++]; if(t == 200001) t = 0; for(int i = head[now]; i; i = e[i].next) { if(e[i].v&&dis[e[i].to] > dis[now] + e[i].c) { from[e[i].to] = i; dis[e[i].to] = dis[now] + e[i].c; if(!inq[e[i].to]) { inq[e[i].to] = 1; q[w++] = e[i].to; if(w == 200001) w = 0; } } } inq[now] = 0; } if(dis[T] >= inf) return 0; return 1;}void mcf() { int i = from[T],x=inf; while(i) { x = min(e[i].v,x); i = from[e[i].from]; } i = from[T]; ans1 = x; while(i) { e[i].v -= x; e[i^1].v += x; ans += e[i].c*x; i = from[e[i].from]; }}int a,b;int main(){ cnt = 1; memset(head,0,sizeof(head)); scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fA,&fB); S = 0,T = 3*n; for(int i = 1; i <= n; ++i){ scanf("%d",&na[i]); insert(S,i,inf,0); insert(S,i+n,inf,f); insert(i+n,T,na[i],0); if(i + 1 <= n) insert(i,i+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); } ans = 0,ans1 = 0; while(spfa()) mcf(); printf("%d\n",ans); return 0;}
费用流做题记录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。