费用流
原来的想法是想限制新到旧的边一定要通过ri 因此 连了(s,u,inf,0)(u,v,ti,0)(u,T,inf,0)这样有一个很大的毛病 跑了一个简单的例子 2天 各需要10个新的 送去洗话费是1，洗1天，买的价格是10，这样建图跑出来的是40 但是期望是22，就是第一天买2个然后送去洗，产生这样的结果的根本原因是没有控制这个最大流，第一种最大流是4第二种是2，跑出来的费用肯定不一样，因此要用到别人的上下界费用转化，<u,v,minf,maxf,c>=<S,v,minf,0>+<u,T,minf,c>+<u,v,maxf-minf,c> 这样才是等价的转化，然后根据题意建边跑一遍费用流就完事了，然后费用流用的是蓝书的板子，核心思想就是和ek算法很像，就是跑出来一条费用最小的可行流，然后流满，然后重建这个图，然后重复知道没有可行流，比dinic还少了个dfs 注意费用会爆int
https://loj.ac/problem/6008
#include#include #include using namespace std;typedef long long int ll;const ll maxn = 2009;const ll inf = 0x3f3f3f3f3f3f3f3f;ll head[maxn*2];ll tot;struct edge{ ll v,nex,w,c;}e[maxn*40];void addedge(ll u,ll v,ll w,ll c){ e[tot] = (edge){v,head[u],w,c}; head[u] = tot++; e[tot] = (edge){u,head[v],0,-c}; head[v] = tot++;}ll dis[maxn*2];ll vis[maxn*2];ll pre[maxn*2];bool spfa(ll S,ll T){ queue q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[S] = 0; vis[S] = 1; q.push(S); while(!q.empty()){ ll now = q.front(); q.pop(); vis[now] = 0; for(ll i=head[now];i!=-1;i=e[i].nex){ ll v = e[i].v; if(e[i].w>0 && dis[v]>dis[now]+e[i].c){ dis[v] = dis[now]+e[i].c; pre[v] = i; if(vis[v]==0){ vis[v] = 1; q.push(v); } } } } if(dis[T]==inf){ return false; } return true;}ll ed(ll S,ll T,ll &flow){ ll p; ll ans = 0; ll sum = inf; for(ll i=T;i!=S;i=e[p^1].v){ p = pre[i]; sum = min(sum,e[p].w); } for(ll i=T;i!=S;i=e[p^1].v){ p = pre[i]; e[p].w-=sum; e[p^1].w+=sum; ans+=(ll)sum*e[p].c; } flow+=sum; return ans;}ll solve(ll S,ll T){ ll ans = 0; ll flow = 0; while(spfa(S,T)){ ans+=ed(S,T,flow); } return ans;}int main(){ memset(head,-1,sizeof(head)); tot = 0; ll n; scanf("%lld",&n); ll p,a1,a2,b1,b2; scanf("%lld%lld%lld%lld%lld",&p,&a1,&a2,&b1,&b2); ll S = 0,T = 1; for(ll i=1;i<=n;i++){ ll t; scanf("%lld",&t); addedge(S,2*i+1,t,0); addedge(2*i,T,t,0); } for(ll i=1;i<=n;i++){ addedge(S,2*i,0x3f3f3f3f,p); if(i