网络流详解(C++版)

网络流基本概念在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj,弧旁的数表示这条运输线的最大通过能力。产品经过交通网从vi到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。图5-2图5-2网络与网络流给一个有向图N=(V,E),在V中指定一点，称为源点(记为vs,和另一点，称为汇点(记为vt),其余的点叫中间点，对于E中每条弧(vi,vj)都对应一个正整数c(vi,vj)^0(或简写成cij)，称为f的容量，则赋权有向图N=(V,E,c,vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点,v4为汇点,弧旁的数字为cij。 所谓网络上的流,是指定义在弧集合E上一个函数f={f(vi,vj)},并称f(vi,vj)为弧(vi,vj)上的流量(下面简记为fij)。如图5-2所示的网络N,弧上两个数，第一个数表示容量cij，第二个数表示流量fij。可行流与最大流在运输网络的实际问题中,我们可以看出,对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0,源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：容量约束：0WfWc,(v,v)WE,ijij ij守恒条件对于中间点：流入量二流出量；对于源点与汇点：源点的净流出量v(f)=汇点的s净流入量(-v(f))t的流f,称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。网络N中流值最大的流f*称为N的最大流。可增广路径所谓可增广路径,是指这条路径上的流可以修改,通过修改,使得整个网络的流值增大。设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：在p上的所有前向弧(vi-vj)都是非饱和弧，即0Wf<cijij在p上的所有后向弧(vi-vj)都是非零弧，即0<fWcjiji则称P为(关于可行流f的)一条可增广路径。最大流定理当且仅当不存在关于f*的增广路径，可行流f*为最大流。5.2最大流算法算法思想:最大流问题实际上是求一可行流{fij},使得v（f）达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f，得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。1.寻求最大流的标号法（Ford,Fulkerson）从一个可行流（一般取零流）开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。（1）标号过程在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。标号开始时，给vs标上（s，0），这时vs是标号但末检查的点，其余都是未标号的点，记为（0，0）。取一个标号而未检查的点vi,对于一切未标号的点vj：对于弧（vi，vj），若fij〈cij，则给vj标号（vi，0），这时，vj点成为标号而未检查的点。对于弧（vi，vj），若fji>0，则给vj标号（-vi，0），这时，vj点成为标号而未检查的点。于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径P，转入调整过程。若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。（2）调整过程从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk（或-vk），则弧（vk，vt）（或相应地（vt，vk））是p上弧。接下来检查vk的第一标号，若为vi（或-vi），则找到（vi,vk）（或相应地（vk，vi））。再检查vi的第一标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：Q=min{min（cij-fij），minf*ij}对流f进行如下的修改：f'ij= fij+Q （vi，vj）wP的前向弧的集合f'ij= fij-Q （vi，vj）eP的后向弧的集合f'ij=f*ij （vi，vj）不属于P的集合接着，清除所有标号，对新的可行流f',重新进入标号过程。Codevs1993草地排水题目描述Description在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。输入描述InputDescription第1行：两个用空格分开的整数N(0<=N<=200)和M(2<=M<=200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。第二行到第N+1行：每行有三个整数，Si,Ei,和Ci。Si和Ei(1<=Si,Ei<=M)指明排水沟两端的交点,雨水从Si流向Ei。Ci(0<=Ci<=10,000,000)是这条排水沟的最大容量。输出描述OutputDescription输出一个整数，即排水的最大流量。样例输入SampleInput5424014204202330410样例输出SampleOutput50Dinic算法：#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>usingnamespacestd;constintmn=22222;constintmm=1000000+5;constintinf=0x3fffffff;//1073741823intn,m,st,sd,cnt;intdis[mn],que[mn],work[mn];intans;structdata{intto;intflow;intnext;inthead;}e[mm];voidinit(){st=1;sd=n;for(inti=1;i<=n;i++){e[i].head=0;}cnt=0;}voidaddedge(intu,intv,intc){cnt++;e[cnt].to=v;e[cnt].flow=c;e[cnt].next=e[u].head;e[u].head=cnt;}boolbfs(){intu,v,l=1,h=0;for(inti=1;i<=n;i++)dis[i]=-1;que[1]=st;dis[st]=0;while(l<h){h++;u=que[h];for(inti=e[u].head;i>0;i=e[i].next){v=e[i].to;if(e[i].flow&&dis[v]<0){dis[v]=dis[u]+1;l++;que[l]=v;if(v==sd)returntrue;}}}returnfalse;}intdfs(intu,intexp){if(u==sd)returnexp;for(inti=work[u];i>0;i=e[i].next){intv=e[i].to,tp;if(e[i].flow&&dis[v]==dis[u]+1&&(tp=dfs(v,min(e[i].flow,exp)))>0){e[i].flow-=tp;e[i+1].flow+=tp;returntp;}}return0;}voidDinic(){while(bfs()){for(inti=0;i<n;i++)work[i]=e[i].head;while(dfs(st,inf));}}intmain(){scanf("%d%d",&m,&n);init();for(inti=1;i<=m;i++){intu,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);addedge(v,u,0);}Dinic();ans=0;for(inti=e[sd].head;i>0;i=e[i].next){intv=e[i].to;ans+=e[i].flow;}printf("%d\n",ans);return0;}SAP算法:#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineMAXN444//邻接表要开边数的2倍structEdge{intv,cap,next;}edge[MAXN];intlevel[MAXN];〃标记层次(距离标号)〃间隙优化，定义gap[i]为标号是i的点的个数〃在重标记i时，检查gap[level[i]]若减为0,这算法结束。intgap[MAXN];intpre[MAXN];〃前驱intcur[MAXN];inthead[MAXN];intNV,NE;//NE为边数，初始化为0；voidInsert(intu,intv,intcap,intcc=0){edge[NE].cap=cap;edge[NE].v=v;edge[NE].next=head[u];head[u]=NE++;edge[NE].cap=cc;edge[NE].v=u;edge[NE].next=head[v];head[v]=NE++;}//参数，源点，汇点intSAP(intvs,intvt){memset(level,0,sizeof(level));memset(pre,-1,sizeof(pre));memset(gap,0,sizeof(gap));〃cur[i]保存的是当前弧for(inti=0;i<=NV;i++)cur[i]=head[i];intu=pre[vs]=vs;〃源点的pre还是其本身intmaxflow=0,aug=-1;gap[0]=NV;while(level[vs]<NV){loop:for(int&i=cur[u];i!=-1;i=edge[i].next){intv=edge[i].v;//v是u的后继//寻找可行弧if(edge[i].cap&&level[u]==level[v]+1){//aug表示增广路的可改进量aug==-1?(aug=edge[i].cap):(aug=min(aug,edge[i].cap));pre[v]=u;u=v;//如果找到一条增广路if(v==vt){maxflow+=aug;//更新最大流；//路径回溯更新残留网络for(u=pre[v];v!=vs;v=u,u=pre[u]){//前向弧容量减少，反向弧容量增加edge[cur[u]].cap-=aug;edge[cur[u]Al].cap+=aug;}aug=-l;}gotoloop;}}intminlevel=NV;//寻找与当前点相连接的点中最小的距离标号(重标号)for(inti=head[u];i!=-l;i=edge[i].next){intv=edge[i].v;if(edge[i].cap&&minlevel>level[v]){cur[u]=i;〃保存弧minlevel=level[v];}}if((--gap[level[u]])==O)break;〃更新gap数组后如果出现断层，则直接退出。level[u]=minlevel+1;〃重标号gap[level[u]]++;//距离标号为level[u]的点的个数+1;u=pre[u];〃转当前点的前驱节点继续寻找可行弧}returnmaxflow;}intmain(){intm;〃边的条数while(~scanf("%d%d",&m,&NV)){memset(head,-1,sizeof(head));NE=0;for(inti=1;i<=m;i++){intu,v,cap;scanf("%d%d%d",&u,&v,&cap);Insert(u,v,cap);}printf("%d\n",SAP(1,NV));}return0;}Codevs1914运输问题题目描述DescriptionW公司有m个仓库和n个零售商店。第i个仓库有ai个单位的货物；第j个零售商店需要bj个单位的货物。货物供需平衡，即sum(si)=sum(bj)。从第i个仓库运送每单位货物到第j个零售商店的费用为cij。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。编程任务：对于给定的m个仓库和n个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。输入描述InputDescription的第1行有2个正整数m和n分别表示仓库数和零售商店数。接下来的一行中有m个正整数ai,1WiWm,表示第i个仓库有ai个单位的货物。再接下来的一行中有n个正整数bj,1WjWn,表示第j个零售商店需要bj个单位的货物。接下来的m行，每行有n个整数，表示从第i个仓库运送每单位货物到第j个零售商店的费用cij。输出描述OutputDescription将计算出的最少运输费用和最多运输费用输出样例输入SampleInput232202801701202107739105150186122样例输出SampleOutput4850069140把所有仓库看做二分图中顶点Xi,所有零售商店看做二分图中顶点Yi,建立附加源S汇To1、 从S向每个Xi连一条容量为仓库中货物数量ai,费用为0的有向边。2、 从每个Yi向T连一条容量为商店所需货物数量bi,费用为0的有向边。3、 从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。这道题其实就是求一个网络中的最小费用最大流和最大费用最大流,最小费用最大流略过,最大费用最大流有2中方法：1、 把所有费用变成相反数做一遍最小费用最大流,输出答案的相反数；2、 初始化spfa时dis数组全从max改为-1，松弛的条件从dis[i]>dis[j]+cap[i,j]改为dis[i]vdis[j]+cap[i,j]；此处我采用了第一种方法。#include<iostream>#include<cstdio>#include<cstring>#defineinf0x7fffffff#defineT2001usingnamespacestd;intm,n,head[2005],q[2005],dis[2005],from[2005],a[2005],b[2005],cnt,ans;intc[2005][2005];boolinq[2005];structdata{intfrom,to,next,v,c;}e[1000001];voidins(intu,intv,intw,intc){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;}voidinsert(intu,intv,intw,intc){ins(u,v,w,c);ins(v,u,0,-c);}voidbuild(intk){cnt=1;memset(head,0,sizeof(head));for(inti=1;i<=m;i++)insert(0,i,a[i],0);for(inti=1;i<=n;i++)insert(m+i,T,b[i],0);for(inti=1;i<=m;i++)for(intj=1;j<=n;j++)insert(i,m+j,inf,k*c[i][j]);}boolspfa(){for(inti=0;i<=T;i++)dis[i]=inf;intt=0,w=1,i,now;dis[0]=q[0]=0;inq[0]=1;while(t!=w){now=q[t];t++;if(t==200)t=0;for(inti=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==200)w=0;}}inq[now]=0;}if(dis[T]==inf)return0;return1;}voidmcf(){inti,x=inf;i=from[T];while(i){x=min(e[i].v,x);i=from[e[i].from];}i=from[T];while(i){e[i].v-=x;e[iA1].v+=x;ans+=x*e[i].c;i=from[e[i].from];}}intmain(){scanf("%d%d",&m,&n);for(inti=1;i<=m;i++)scanf("%d",&a[i]);for(inti=1;i<=n;i++)scanf("%d",&b[i]);for(inti=1;i<=m;i++)for(intj=1;j<=n;j++)scanf("%d",&c[i][j]);build(1);while(spfa())mcf();printf("%d\n",ans);ans=0;build(-1);while(spfa())mcf();printf("%d\n",-ans);return0;}NOI2006最大获利题目描述Description新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（lWiWN）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai,Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（lWiWM,1WAi,BiWN）THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利=获益之和-投入成本之和）输入描述InputDescription输入文件中第一行有两个正整数N和M。第二行中有N个整数描述每一个通讯中转站的建立成本，依次为Pl,P2,…,PN。以下M行，第（i+2）行的三个数Ai,Bi和Ci描述第i个用户群的信息。所有变量的含义可以参见题目描述。输出描述OutputDescription你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。样例输入SampleInput5523452334l33l42453样例输出SampleOutput4数据范围及提示DataSize&Hint选择建立1、2、3号中转站，则需要投入成本6,获利为10,因此得到最大收益4。80%的数据中：NW200,MW1000。100%的数据中：NW5000，MW50000，0WCiW100,0WPiW100。代码建立一個有N+M+2個點，3M+N條邊的圖。其中，有一個超級源S，N個中轉站，M個用戶和一個超级汇T；S到每個中轉站連一條以該中轉站成本為權值的邊，從每一個中轉站到每一個能夠與它通訊的用戶連一條以正無窮為權值的邊，再從每一個用戶到超級匯連一條以該用戶帶來的收益為權值的邊。所求結果即為所有用戶帶來收益的總和減去最大流（證明略）。#include<iostream>#include<cstdio>#include<cstring>#defineINF0x7fffffffusingnamespacestd;structdata{intnext,to,v;}e[500001];intn,m,ans;intne=1;intq[60001],head[60001],h[60001];voidinsert(intu,intv,intw){ne++;e[ne].to=v;e[ne].v=w;e[ne].next=head[u];head[u]=ne;ne++;e[ne].to=u;e[ne].next=head[v];head[v]=ne;}boolbfs(){intnow,t=0,w=1,p,i;memset(h,-1,sizeof(h));q[t]=h[0]=0;while(t<w){now=q[t];t++;i=head[now];while(i){if(e[i].v&&h[e[i].to]<0){q[w++]=e[i].to;h[e[i].to]=h[now]+1;}i=e[i].next;}}if(h[n+m+1]==-1)return0;return1;}intdfs(intx,intf){if(x==n+m+1)returnf;inti=head[x];intw,used=0;while(i){if(e[i].v&&h[e[i].to]==h[x]+1){w=f-used;w=dfs(e[i].to,min(w,e[i].v));e[i].v-=w;e[iA1].v+=w;used+=w;if(used==f)returnf;}i=e[i].next;}if(!used)h[x]=-1;returnused;}voiddinic(){while(bfs())ans+=dfs(0,INF);}intmain(){intsum=0;scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){inta;scanf("%d",&a);insert(0,i,a);}for(inti=1;i<=m;i++){inta,b,c;scanf("%d%d%d",&a,&b,&c);insert(a,n+i,INF);insert(b,n+i,INF);insert(n+i,n+m+1,c);sum+=c;}dinic();printf("%d",sum-ans);return0;}Codevs1033蚯蚓的游戏问题题目描述Description在一块梯形田地上，一群蚯蚓在做收集食物游戏。蚯蚓们把梯形田地上的食物堆积整理如下a(l,l)a(l,2)...a(l,m)a(2,l)a(2,2)a(2,3)...a(2,m)a(2,m+l)a(n,l)a(n,2) a(n,3)... a(n,m+n-l)它们把食物分成n行，第1行有m堆的食物，每堆的食物量分别是a(1,1),a(1,2),…,a(1,m)；第2行有m+1堆食物，每堆的食物量分别是a(2,1),a(2,2),…，a(2,m+1)；以下依次有m+2堆、m+3堆、…m+n-1堆食物。现在蚯蚓们选择了k条蚯蚓来测试它们的合作能力(1WkWm)。测试法如下：第1条蚯蚓从第1行选择一堆食物，然后往左下或右下爬，并收集1堆食物，例如从a(1,2)只能爬向a(2,2)或a(2,3),而不能爬向其它地方。接下来再爬向下一行收集一堆食物，直到第n行收集一堆食物。第1条蚯蚓所收集到的食物量是它在每一行所收集的食物量之和；第2条蚯蚓也从第1行爬到第n行，每行收集一堆食物，爬的方法与第1条蚯蚓相类似，但不能碰到第1条蚯蚓所爬的轨迹；一般地，第i条蚯蚓从第1行爬到第n行，每行收集一堆食物，爬的方法与第1条蚯蚓类似，但不能碰到前I-1条蚯蚓所爬的轨迹。这k条蚯蚓应该如何合作，才能使它们所收集到的食物总量最多？收集到的食物总量可代表这k条蚯蚓的合作水平。0编程任务：给定上述梯形m、n和k的值(1WkWmW30;1WnW30)以及梯形中每堆食物的量(小于10的非整数)，编程计算这k条蚯蚓所能收集到的食物的最多总量。输入描述InputDescription输入数据由文件名为INPUT1.*的文本文件提供，共有n+1行。每行的两个数据之间用一个空格隔开。•第1行是n、m和k的值。接下来的n行依次是梯形的每一行的食物量a(i,1)，a(i,2)，„，a(i,m+i-1)，i=1,2,…,n。输出描述OutputDescription程序运行结束时，在屏幕上输出k蚯蚓条所能收集到的食物的最多总量。样例输入SampleInput2 21250211006样例输出SampleOutput26很裸的最小费用流。每个食物拆成两个点，之间连一条权值为-a[i][j](由于是求最大值，所以要取相反数)，容量为1的边。食物与食物之连接一条权值为0，容量为1的边。第一排的食物与源点连一条权值为0，容量为1的边。每个食物都与汇点连一条权值为0,容量为1的边。最后求一个流量为k的最小费用流。这题也是很水的费用流啊，同之前那题一样，拆点然后建边，容量为1，费用为点权。然后建个源连第一行每个点，容量为1，费用为0，然后最后一行每个点连汇，容量为1，费用为0。最后再建个超级源连一条边到源，容量为k，费用为0。再建个超级汇，汇连边到它，容量为k,费用为0。跑一次费用流即可。

(LO)(hI)1,0)0)0)0)T胃2(l+O)(IJIO)(146)(I®(l4^1,0)(Lj2)(Li1)如){I.(LO)(hI)1,0)0)0)0)T胃2(l+O)(IJIO)(146)(I®(l4^1,0)(Lj2)(Li1)如){I.0<(14)it：弧上时数宇为(鴻斶分析与构图续2考虑到原图的缺陷，我们可以把每个顶点(x,yj拆成两个顶点；(x,y)J和(尼yF°然后按照下述规则重新构造弧：LI若原来有弧＜(xl,y1)©2,y2)＞,则在＜(xl,y1*(x2,y2)i＞之间连一条弧，弧的容量设为I,收益设为0。2. 2在(xl.yl)'和0d,yl)2之间连一条弧，弧的容量设为1，收益等于原来(xl,yl)上的食物量。通过把一个点拆为两个，我们就把点上的权转移到了边上，而口由于被拆开的两个点之间的弧容量是1，所以也能够解决“路线不重叠”限制了◎设立两个点S\T\表示“所有源的源”和“所有汇的汇”，这样原图就转化为单源单汇的图了。问题即为求图的最大收益流。如图2。分析与构图续3对于k条蚯蚓，…种想法是再增加一个附加源S3它发出一条弧指向S\并11弧上的容量是k,收益是0。这样，当我们求岀这个图的最大流的时候，＜sJ\sJ＞上的流量肯定等于灯另」种是换一个角度来考虑，因为在求最大流时，每次找可增广道路时总是填满1条蚯蚓的路径”所以我们只要找k条可增广道路就是k条蚯蚓爬了一遍了。上面的模型是最大收益流的模型，我们可以把每条弧上的收益转化成•个常数n^x减去收益的差(这个常数要保证大于最大收益，在这里可以取J0),把模型转化为最小费用流问题，这样我们求出最小费用吐后，用max^n^k-a得到最大收益。#include<cstdio>#include<iostream>#defineLLlonglong#defineinf0x3ffffff#defineS0#defineT2*tot+2#defineSS2*tot+1#defineN5010usingnamespacestd;LLread(){LLx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}returnx*f;}structedge{intfrom,to,next,c,v;}e[1000010];intn,m,k,cnt=1,tot,now,ans;inthead[N],from[N],q[N],dist[N];boolmrk[N];voidins(intu,intv,intw,intc){e[++cnt].to=v;e[cnt].from=u;e[cnt].v=w;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt;}voidinsert(intu,intv,intw,intc){ins(u,v,w,c);ins(v,u,0,-c);}boolspfa(){for(inti=0;i<=T;i++)dist[i]=inf;intt=0,w=1;dist[S]=0;q[0]=S;mrk[S]=1;while(t!=w){intnow=q[t++];if(t==2005)t=0;for(inti=head[now];i;i=e[i].next)if(e[i].v&&dist[now]+e[i].c<dist[e[i].to]){dist[e[i].to]=dist[now]+e[i].c;from[e[i].to]=i;if(!mrk[e[i].to]){mrk[e[i].to]=1;q[w++]=e[i].to;if(w==2005)w=0;}}mrk[now]=0;}returndist[T]!=inf;}voidmcf(){intx=inf;for(inti=from[T];i;i=from[e[i].from])x=min(x,e[i].v);for(inti=from[T];i;i=from[e[i].from]){e[i].v-=x;e[iA1].v+=x;ans-=x*e[i].c;}}intmain(){n=read();m=read();k=read();for(inti=1;i<=n;i++)tot+=m+i-1;insert(S,SS,k,0);for(inti=1;i<=m;i++)insert(SS,i,1,0);for(inti=0;i<n+m-1;i++)insert(2*tot-i,T,1,0);for(inti=1;i<=n;i++)for(intj=1;j<=m+i-1;j++){now++;intx=read();insert(now,now+tot,1,-x);if(i!=n){insert(tot+now,now+m+i-1,1,0);insert(tot+now,now+m+i,1,0);}}while(spfa())mcf();printf("%d\n",ans);Codevs1227方格取数2题目描述Description给出一个n*n的矩阵，每一格有一个非负整数Aij,(Aij<=1000)现在从(1,1)出发，可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来，该格子的数就变成0,这样一共走K次，现在要求K次所达到的方格的数的和最大输入描述InputDescription第一行两个数n,k(1<=n<=50,0<=k<=10)接下来n行，每行n个数，分别表示矩阵的每个格子的数输出描述OutputDescription一个数,为最大和样例输入SampleInput31123021142样例输出SampleOutput11#include<cstdio>#include<cstring>#include<iostream>#defineINF0x7fffffff#defineN6001#defineM1000010usingnamespacestd;structdata{intfrom,to,v,c,next;}e[M];longlongans;intn,k,dis[N],head[N],from[N],q[M],cnt=1;boolinq[N];voidinsert(intu,intv,intw,intc){e[++cnt].from=u;e[cnt].to=v;e[cnt].v=w;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt;}voidins(intu,intv,intw,intc){insert(u,v,w,c);insert(v,u,0,-c);}boolspfa(){intt=0,w=1,i,now;memset(dis,-1,sizeof(dis));q[0]=0;inq[0]=1;dis[0]=0;while(t<w){now=q[t++];i=head[now];while(i){if(e[i].v>0&&dis[now]+e[i].c>dis[e[i].to]){dis[e[i].to]=dis[now]+e[i].c;from[e[i].to]=i;if(!inq[e[i].to]){q[w++]=e[i].to;inq[e[i].to]=true;}}i=e[i].next;inq[now]=false;}}if(dis[6000]==-1)returnfalse;elsereturntrue;}voidmincf(){inti=from[6000],sum=INF;while(i){sum=min(sum,e[i].v);i=from[e[i].from];}i=from[6000];while(i){e[i].v-=sum;e[iT].v+=sum;ans+=sum*e[i].c;i=from[e[i].from];}}intmain(){scanf("%d%d",&n,&k);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){intx;scanf("%d",&x);ins((i-1)*n+j,(i-1)*n+j+n*n,1,x);ins((i-1)*n+j,(i-1)*n+j+n*n,k,0);if(j<n)ins((i-1)*n+j+n*n,(i-1)*n+j+1,k,0);if(i<n)ins((i-1)*n+j+n*n,i*n+j,k,0);}ins(0,1,k,0);ins(2*n*n,6000,k,0);while(spfa())mincf();printf("%lld",ans);return0;}Codevs1034家园题目描述Description由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空站处于地球与月球之间(编号1..n)，m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi,将周期性地停靠一系列的太空站(Sil,Si2„Sir),如：(1,3,4)表示停靠太空站134134134…。任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站(或地球、月球)时上船或下船。初始时的人全在地球上，太空船全在初始站(太空船pi处于Si1),目标是让所有的人尽快地全部转移到月球上。输入描述InputDescription文件第一行为三个正整数n(太空站个数)、m(太空船个数)、k(需要运送的地球上的人的个数)，其中1<=m<=13,1<=n<=20,1<=k<=50。接下来的n行给出了太空船的信息，第i+1行说明太空船pi，此行第一个数表示pi可容纳的人数Hpi,第二个数表示pi停靠一个周期的太空站个数 r，1<=r<=n+2,随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir),地球用0表示，月球用-1表示。0时刻时，所有太空船都在初始站，随后开始运行，在时刻1,2,3…等正点时刻各艘太空船停靠相应的太空站，即人只有在0,1,2…等正点时刻才能上下太空船。输出描述OutputDescription文件只有一个数，若问题有解，输出完成全部人员安全转移的时刻，否则输出0。样例输入SampleInput221130121312-1样例输出SampleOutput5分析：枚举时间t,每增加一单位时间，就增加一列点，这一列的点的序号是(0,t),(1,t)...(n,t)，其中第一个数字表示太空站(0是地球，n是月球)，第二个数字表示的是时间。然后从(i,t-1)到(i,t)连一条容量为INF的边(太空站可以停留无限的人)，从地球(超级源点)连一条INF的边到(0,t)，从(n,t)连一条INF的边到月球(超级汇点)，然后考虑所有的太空船，设其中一个太空船的移动为a0,a1,a2....aT-1,那么连接一条从(a[(t-1)%T],t-1)到(a[t%T],t)，容量为此太空船容量的边，求最大流，如果最大流的大于了总人数，就跳出，答案就是当前的时间。#include<iostream>#include<cstdio>#include<cstring>#defineinf0x7fffffffusingnamespacestd;intn,m,k,T,cnt=1;inta[25][25],s[25],H[25];intq[4001],h[4001],head[4001];structdata{intto,next,v;}e[50001];voidins(intu,intv,intw){cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;}voidinsert(intu,intv,intw){ins(u,v,w);ins(v,u,0);}voidadd(){for(inti=0;i<=n+1;i++)insert(i+(T-1)*22,i+T*22,inf);for(inti=1;i<=m;i++){intu=(T-1)*22+a[i][(T-1)%s[i]+1];intv=T*22+a[i][T%s[i]+1];insert(u,v,H[i]);}}boolbfs(){intt=0,w=1,i,now;memset(h,-1,sizeof(h));h[0]=q[0]=0;while(t<w){now=q[t];t++;i=head[now];while(i){if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}i=e[i].next;}}if(h[1+n+T*22]==-1)return0;return1;}intdfs(intx,intf){if(x==1+n+T*22)returnf;inti=head[x];intw,used=0;while(i){if(e[i].v&&h[e[i].to]==h[x]+1){w=f-used;w=dfs(e[i].to,min(w,e[i].v));e[i].v-=w;e[iA1].v+=w;used+=w;if(used==f)returnf;}i=e[i].next;}if(!used)h[x]=-1;returnused;}voiddinic(){while(bfs())k-=dfs(0,inf);}intmain(){scanf("%d%d%d",&n,&m,&k);for(inti=1;i<=m;i++){scanf("%d%d",&H[i],&s[i]);for(intj=1;j<=s[i];j++){scanf("%d",&a[i][j]);if(a[i][j]==