php网站开发实例教程百度,网站备案查询,网站设计制作工作室,响应式网站建设信息正题 题目大意
若干个城市一些城市有一定的电#xff0c;有些城市需要一定的电。对于第iii个城市购买一个电需要iniin_iini#xff0c;送出电需要outiout_iouti。当然城市之间也可以相互传输电。
对于一条电缆(x,y,a,b,l,r)(x,y,a,b,l,r)(x,y,a,b,l,r)表示x−yx-有些城市需要一定的电。对于第iii个城市购买一个电需要iniin_iini送出电需要outiout_iouti。当然城市之间也可以相互传输电。
对于一条电缆(x,y,a,b,l,r)(x,y,a,b,l,r)(x,y,a,b,l,r)表示x−gt;yx-gt;yx−y的单向传输传输kkk个的话要ak2bkak^2bkak2bk传输电量的上下界为[l..r][l..r][l..r]。
要求每个城市都没有多余也不缺少电求最小代价。 解题思路
显然费用流。
首先流量表示电十分显然。
因为有上下界所以我们动态开点且费用流时每次只流一个流量。
然后我们考虑如何构图。
购买:s−gt;is-gt;is−i流量为infinfinf费用为iniin_iini 送出:i−gt;ei-gt;ei−e流量为infinfinf费用为outiout_iouti
但是我们会发现流量是无限大的。
这时我们就要考虑了因为流量是一个一个流的只要我们让流量每次都优先是使用原来的就可以了
多余(leftgt;0):s−gt;i(leftgt;0):s-gt;i(left0):s−i流量为leftleftleft费用为−inf-inf−inf 缺少(leftlt;0):s−gt;i(leftlt;0):s-gt;i(left0):s−i流量为−left-left−left费用为−inf-inf−inf
这样就可以保证每次优先流已经有的直到我们发现最小费用的路径长度大于000就可以退出了(因为这时已经没有需要补充也没有多余的电了)。
但是这样费用就是负数了。其实我们只要把多出的−inf-inf−inf减去就好了。也就是(ans%infinf)%inf(ans\%infinf)\%inf(ans%infinf)%inf
之后我们考虑连边因为有上下界对于每条边(x,y,a,b,l,r)(x,y,a,b,l,r)(x,y,a,b,l,r) 我们可以让leftxleft_xleftx减去lll且leftyleft_ylefty加上lll。也就是让lll开始就流走并直接统计入费用当中。
之后我们考虑费用我们将ak2bkak^2bkak2bk分成若干条流量为1的边然后每次费用为ak2bk−a(k−1)2−b(k−1)ak^2bk-a(k-1)^2-b(k-1)ak2bk−a(k−1)2−b(k−1)也就是ab,3ab,5ab,7ab......ab,3ab,5ab,7ab......ab,3ab,5ab,7ab......。然后根据最小费用原则若这条边要走kkk个流量那必定是前kkk条。
结束但是这样会TLETLETLE。这时我们就需要动态开点。
首先我们对于每条边先只连接着一条边当新的流量流过这条边时我们就在增加一条边。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#includequeue
#define p(x,y) (x*10-4y)
#define ll long long
using namespace std;
const ll N210,M610,inf1000000;
struct node{ll to,next,w,c;
}a[M*20];
ll n,m,ls[N],s,e,tot1,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];
queuell q;
void addl(ll x,ll y,ll w,ll c)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;
}
void change()
{for(ll i1;im;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 xq.front();q.pop();v[x]0;for(ll ils[x];i;ia[i].next){if(!a[i].w) continue;ll ya[i].to;if(f[x]a[i].cf[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 nowe;sumf[e];while(now!s){ll xa[pre[now]^1].to,ya[pre[now]].to;a[pre[now]].w--;a[pre[now]^1].w;cost[x][y];cost[y][x]--;nowa[pre[now]^1].to;}
}
void net_flow()
{while(spfa())count_cost();
}
int main()
{scanf(%lld%lld,n,m);sn1;es1;for(ll i1;in;i){ll in,out;scanf(%lld%lld%lld,left[i],in,out);addl(s,i,inf,in);addl(i,e,inf,out);}for(ll i1;im;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];sumA[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 i1;in;i){if(left[i]0) addl(s,i,left[i],-inf);else addl(i,e,-left[i],-inf);}net_flow();sumsum%inf;if(sum0) suminf;printf(%lld,sum);
}
