正題

---

題目大意

若干個城市一些城市有一定的電，有些城市需要一定的電。對于第$i$個城市購買一個電需要$i{n}_i$，送出電需要$ou{t}_i$。當然城市之間也可以相互傳輸電。

對于一條電纜$(x,y,a,b,l,r)$表示$x?>y$的單向傳輸，傳輸$k$個的話要$a{k}^2+bk$，傳輸電量的上下界為$[l..r]$。

要求每個城市都沒有多余也不缺少電，求最小代價。

---

解題思路

顯然費用流。

首先流量表示電（十分顯然）。

因為有上下界所以我們動態開點且費用流時每次只流一個流量。

然后我們考慮如何構圖。

購買:$s?>i$流量為$inf$費用為$i{n}_i$
送出:$i?>e$流量為$inf$費用為$ou{t}_i$

但是我們會發現流量是無限大的。

這時我們就要考慮了，因為流量是一個一個流的，只要我們讓流量每次都優先是使用原來的就可以了

多余$(left>0):s?>i$流量為$left$費用為$?inf$
缺少$(left<0):s?>i$流量為$?left$費用為$?inf$

這樣就可以保證每次優先流已經有的，直到我們發現最小費用的路徑長度大于$0$就可以退出了(因為這時已經沒有需要補充也沒有多余的電了)。

但是這樣費用就是負數了。其實我們只要把多出的$?inf$減去就好了。也就是$(ans\%inf+inf)\%inf$

之后我們考慮連邊，因為有上下界，對于每條邊$(x,y,a,b,l,r)$
我們可以讓$lef{t}_x$減去$l$且$lef{t}_y$加上$l$。也就是讓$l$開始就流走并直接統計入費用當中。

之后我們考慮費用，我們將$a{k}^2+bk$分成若干條流量為1的邊，然后每次費用為$a{k}^2+bk?a(k?1{)}^2?b(k?1)$也就是$a+b,3a+b,5a+b,7a+b......$。然后根據最小費用原則，若這條邊要走$k$個流量，那必定是前$k$條。

結束，但是這樣會$TLE$。這時我們就需要動態開點。

首先我們對于每條邊先只連接著一條邊，當新的流量流過這條邊時我們就在增加一條邊。

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define p(x,y) (x*10-4+y) #define ll long long using namespace std; const ll N=210,M=610,inf=1000000; struct node{ll to,next,w,c; }a[M*20]; ll n,m,ls[N],s,e,tot=1,sum,left[N],cost[N][N]; ll pre[N],f[N],x[M],y[M],L[M],A[M],B[M],U[M]; bool v[N]; queue<ll> q; void addl(ll x,ll y,ll w,ll c) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c; } void change() {for(ll i=1;i<=m;i++)if(cost[x[i]][y[i]]==L[i]&&L[i]<U[i])L[i]++,addl(x[i],y[i],1,A[i]*(2*L[i]-1)+B[i]); } bool spfa() {change();memset(f,0x3f,sizeof(f));q.push(s);v[s]=1;f[s]=0;while(!q.empty()){ll x=q.front();q.pop();v[x]=0;for(ll i=ls[x];i;i=a[i].next){if(!a[i].w) continue;ll y=a[i].to;if(f[x]+a[i].c<f[y]){pre[y]=i;f[y]=f[x]+a[i].c;if(!v[y])q.push(y),v[y]=1;}}}return f[e]<=0; } void count_cost() {ll now=e;sum+=f[e];while(now!=s){ll x=a[pre[now]^1].to,y=a[pre[now]].to;a[pre[now]].w--;a[pre[now]^1].w++;cost[x][y]++;cost[y][x]--;now=a[pre[now]^1].to;} } void net_flow() {while(spfa())count_cost(); } int main() {scanf("%lld%lld",&n,&m);s=n+1;e=s+1;for(ll i=1;i<=n;i++){ll in,out;scanf("%lld%lld%lld",&left[i],&in,&out);addl(s,i,inf,in);addl(i,e,inf,out);}for(ll i=1;i<=m;i++){scanf("%lld%lld%lld%lld%lld%lld",&x[i],&y[i],&A[i],&B[i],&L[i],&U[i]);left[x[i]]-=L[i];left[y[i]]+=L[i];sum+=A[i]*L[i]*L[i]+B[i]*L[i];cost[x[i]][y[i]]+=L[i];cost[y[i]][x[i]]-=L[i];}for(ll i=1;i<=n;i++){if(left[i]>0) addl(s,i,left[i],-inf);else addl(i,e,-left[i],-inf);}net_flow();sum=sum%inf;if(sum<0) sum+=inf;printf("%lld",sum); }

總結

以上是生活随笔為你收集整理的jzoj3302-[集训队互测2013]供电网络【上下界网络流,费用流,动态加边】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。