高效的最大流sap+邻接表模版
/*
最大流模板
isap复杂度(v^2*e)
*/
/*
*State:HDU42803609MS8860K3571BC++
*题目大意：
*有N个岛屿M条无向路每个路有一最大允许的客流量，求从最西的那个岛屿最多能运
*用多少乘客到最东的那个岛屿。
*解题思路：
*很单纯的网络流，重点是卡时间模板的高效性很重要啊该模板详解
*参见这里模板题就不注释了
*解题感想：
*10000ms的时间里，大多数最大流算法都挂掉了，就这个坚持下来了，用了3000ms左右。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#defineVM100010
#defineEM400010
usingnamespacestd;
constintinf=0x3f3f3f3f;
structE
{
intto,frm,nxt,cap;
}edge[EM];
inthead[VM],e;//建图时初始化
intdep[VM],gap[VM];//ISAP函数内初始化
voidinit()
{
e=0;
memset(head,-1,sizeof(head));
}
voidaddEdge(intcu,intcv,intcw)
{
edge[e].frm=cu;
edge[e].to=cv;
edge[e].cap=cw;
edge[e].nxt=head[cu];
head[cu]=e++;
edge[e].frm=cv;
edge[e].to=cu;
edge[e].cap=0;
edge[e].nxt=head[cv];
head[cv]=e++;
}
intque[VM];
voidBFS(intdes)
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=1;
intfront=0,rear=0;
dep[des]=0;
que[rear++]=des;
intu,v;
while(front!=rear)
{
u=que[front++];
front=front%VM;
for(inti=head[u];i!=-1;i=edge[i].nxt)
{
v=edge[i].to;
if(edge[i].cap!=0||dep[v]!=-1)
continue;
que[rear++]=v;
rear=rear%VM;
++gap[dep[v]=dep[u]+1];
}
}
}
intcur[VM],stack[VM];
//sap模板
intISAP(intsrc,intdes,intn)//源点、汇点、图中点的总数
{
intres=0;
BFS(des);
inttop=0;
memcpy(cur,head,sizeof(head));
intu=src,i;
while(dep[src]<n)
{
if(u==des)
{
inttemp=inf,inser=n;
for(i=0;i!=top;++i)
if(temp>edge[stack[i]].cap)
{
temp=edge[stack[i]].cap;
inser=i;
}
for(i=0;i!=top;++i)
{
edge[stack[i]].cap-=temp;
edge[stack[i]^1].cap+=temp;
}
res+=temp;
top=inser;
u=edge[stack[top]].frm;
}
if(u!=des&&gap[dep[u]-1]==0)
break;
for(i=cur[u];i!=-1;i=edge[i].nxt)
if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
break;
if(i!=-1)
{
cur[u]=i;
stack[top++]=i;
u=edge[i].to;
}
else
{
intmin=n;
for(i=head[u];i!=-1;i=edge[i].nxt)
{
if(edge[i].cap==0)
continue;
if(min>dep[edge[i].to])
{
min=dep[edge[i].to];
cur[u]=i;
}
}
--gap[dep[u]];
++gap[dep[u]=min+1];
if(u!=src)
u=edge[stack[--top]].frm;
}
}
returnres;
}
intmain()
{
#ifndefONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
intn,m,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
intx,y,src,des;
intMin=inf,Max=-inf;
for(inti=1;i<=n;++i)//找出起点src终点des
{
scanf("%d%d",&x,&y);
if(x<=Min)
{
src=i;
Min=x;
}
if(x>=Max)
{
des=i;
Max=x;
}
}
init();
intu,v,c;
for(inti=0;i!=m;++i)
{
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
addEdge(v,u,c);
}
intans=ISAP(src,des,n);
printf("%d\n",ans);
}
return0;
}
//Isap邻接矩阵版模板
//HDU3549Isap邻接矩阵版
//46ms
#include<iostream>
#include<cstring>
#include<cstdio>
#defineM16
usingnamespacestd;
constintinf=0x3f3f3f3f;
intmaze[M][M];
intgap[M],dis[M],pre[M],cur[M];
voidinit()
{
memset(maze,0,sizeof(maze));
}
//起点是0，终点是n-1,nodenum为点的个数
intISAP(ints,intt,intnodenum){
memset(cur,0,sizeof(cur));
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
intu=pre[s]=s,maxflow=0,aug=inf;
gap[0]=nodenum;
while(dis[s]<nodenum){
loop:
for(intv=cur[u];v<nodenum;v++)if(maze[u][v]&&dis[u]==dis[v]+1){
aug=min(aug,maze[u][v]);
pre[v]=u;
u=cur[u]=v;
if(v==t){
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u]){
maze[u][v]-=aug;
maze[v][u]+=aug;
}
aug=inf;
}
gotoloop;
}
intmindis=nodenum-1;
for(intv=0;v<nodenum;v++)if(maze[u][v]&&mindis>dis[v]){
cur[u]=v;
mindis=dis[v];
}
if((--gap[dis[u]])==0)break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
returnmaxflow;
}
intmain(void)
{
#ifndefONLINE_JUDGE
freopen("HDU3549.txt","r",stdin);
#endif
intn,m,cas,cas_c=1;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
init();
intu,v,w;
for(inti=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
u--,v--;
maze[u][v]+=w;
}
intsol=ISAP(0,n-1,n);//起点，终点
printf("Case%d:%d\n",cas_c++,sol);
}
return0;
}
//State:HDU4280居然用了2700ms+,牛逼模版
/*
ThisProblembeatmecompletely.
Beatmytemplatecompletely.
Beatmyfuntioncomletely.
Wastemytimecomletely.
It'sanakedmaximum-streamproblem.
Themainpointisyourtemplate.
ItmakemerealizethatmySAPtemplateisash*t!
....TomakemySAPfaster,Ihavedonethreekindsofoptimization.
1.Recordtheadjacencynodewhichhasminimumdistance;
2.InitailizethedistancebyusingBFS;
3.AsIgotaStack-Overflow,IsimulatetheDFSbyusingstackinSTL;
ThenIgotACin2s+.
Ofcourse,theproblemisalsocorrespondtotheMinimum-CutinDual-Graph.
Hence,Dijkstrawithminimumheapisoptimalalgorithm.
*/
//Header
//#include<cstdio>
//#include<cstdlib>
//#include<iostream>
//#include<cstring>
//#include<string>
//#include<vector>
//#include<map>
//#include<algorithm>
//#include<cctype>
//#include<queue>
//#include<stack>
//#include<cmath>
//usingnamespacestd;
////Macro
////STL-Alias
//#defineUN(c,a)unique(c,a)
//#defineMS(c,a)memset(c,a,sizeofc)
//#defineFLC(c,a,b)fill(c,c+a,b)
//#defineLOS(c,a,b)lower_bound(c,a,b)
//#defineUPS(c,a,b)upper_bound(c,a,b)
////Syntax-Alias
//#defineRep(c,a,b)for(intc=(a);c<(b);c++)
//#defineNre(c,a,b)for(intc=(a);c>(b);c--)
////DEBUG
//#defineFKputs("Fu*khere!")
//#definePA(s,c,a,b,p,f){\
//printf(s);\
//Rep(c,a,b)printf(p,(f));\
//puts("");}
////Constant
//#defineINFL(0x7fffffffffffffffLL)
//#defineINFI(0x7fffffff)
//#defineMOD()
//#defineMAXN(100005)
////Type-Alias
//typedeflonglongLL;
//typedeflongdoubleLD;
//typedefintAI[MAXN];
//typedefboolAB[MAXN];
//typedefdoubleAD[MAXN];
//typedefLLALL[MAXN];
//typedefLDALD[MAXN];
//
//
////FSG
//structEdge
//{
//intv,w,next;
//};
//vector<Edge>E;
//AIL;
//voidG_ini()
//{
//E.clear();
//MS(L,-1);
//}
//voidAE(intu,intv,intw)
//{
//Edgete={v,w,L[u]};
//L[u]=E.size();
//E.push_back(te);
//}
//#defineEre(c,a,L)for(intc=L[a];c!=-1;c=E[c].next)
//
//
////ISAP
//intISAP(intsrc,intsnk,intV)
//{
//staticAIdis,gap,_L,se;
//intu=src,mxf=0,te=0;
//memcpy(_L,L,sizeofL);
//MS(dis,-1);MS(gap,0);
//gap[dis[snk]=0]=1;
//queue<int>Q;
//Q.push(snk);
//while(!Q.empty())
//{
//intu=Q.front();Q.pop();
//Ere(i,u,L)if(E[i].w&&dis[E[i].v]<0)
//{
//gap[dis[E[i].v]=dis[u]+1]++;
//Q.push(E[i].v);
//}
//}
//while(dis[src]<V)
//{
//int_i=-1;
//Ere(i,u,_L)if(E[i].w&&dis[u]==dis[E[i].v]+1)
//{
//_i=i;
//break;
//}
//if(_i!=-1)
//{
//_L[u]=_i;
//u=E[se[te++]=_i].v;
//}
//else
//{
//intmd=INFI;
//_i=-1;
//Ere(i,u,L)if(E[i].w&&dis[E[i].v]<md)
//{
//md=dis[E[i].v];
//_L[u]=i;
//}
//if(!--gap[dis[u]])break;
//gap[dis[u]=md+1]++;
//if(u!=src)u=E[se[te---1]^1].v;
//}
//if(u==snk)
//{
//int_i=0,mf=INFI;
//Rep(i,0,te)if(E[se[i]].w<mf)
//{
//mf=E[se[i]].w;
//_i=i;
//}
//Rep(i,0,te)
//{
//E[se[i]].w-=mf;
//E[se[i]^1].w+=mf;
//}
//mxf+=mf;
//te=_i;
//u=E[se[_i]^1].v;
//}
//}
//returnmxf;
//}
//
//
//structIsl
//{
//intx,y;
//voidinp()
//{
//scanf("%d%d",&x,&y);
//}
//}I[MAXN];
//intn,m;
//
//
//intmain()
//{
//intT;
//scanf("%d",&T);
//while(T--)
//{
////Initialize
//scanf("%d%d",&n,&m);
//I[0].inp();
//intsrc=0,snk=0;
//Rep(i,1,n)
//{
//I[i].inp();
//if(I[i].x<I[src].x)src=i;
//if(I[i].x>I[snk].x)snk=i;
//}
//G_ini();
//while(m--)
//{
//intu,v,w;
//scanf("%d%d%d",&u,&v,&w);
//u--;
//v--;
//AE(u,v,w);
//AE(v,u,w);
//}
////Solve
//printf("%d\n",ISAP(src,snk,n));
//}
//return0;
//}
//
//
//
//
//
//
////isap深搜版，以HDU4280长春网络赛的题目为例，不过那题10000ms都TLE
////不知道dfs版有什么长处，据说dfs版比dinic要快。
//#include<iostream>
//usingnamespacestd;
//
//typedefstruct{intv,next,val;}edge;
//constintMAXN=100005;
//constintMAXM=500010;
//constintinf=0x3f3f3f3f;
//edgee[MAXM];
//intp[MAXN],eid;
//
//inlinevoidinit(){memset(p,-1,sizeof(p));eid=0;}
//
////有向
//inlinevoidinsert1(intfrom,intto,intval)
//{
//e[eid].v=to;
//e[eid].val=val;
//e[eid].next=p[from];
//p[from]=eid++;
//
//swap(from,to);
//
//e[eid].v=to;
//e[eid].val=0;
//e[eid].next=p[from];
//p[from]=eid++;
//}
//
////无向
//inlinevoidinsert2(intfrom,intto,intval)
//{
//e[eid].v=to;
//e[eid].val=val;
//e[eid].next=p[from];
//p[from]=eid++;
//
//swap(from,to);
//
//e[eid].v=to;
//e[eid].val=val;
//e[eid].next=p[from];
//p[from]=eid++;
//}
//
//intn,m;//n为点数m为边数
//inth[MAXN];
//intgap[MAXN];
//
//intsource,sink;
//inlineintdfs(intpos,intcost)
//{
//if(pos==sink)
//{
//returncost;
//}
//
//intj,minh=n-1,lv=cost,d;
//
//for(j=p[pos];j!=-1;j=e[j].next)
//{
//intv=e[j].v,val=e[j].val;
//if(val>0)
//{
//if(h[v]+1==h[pos])
//{
//if(lv<e[j].val)d=lv;
//elsed=e[j].val;
//
//d=dfs(v,d);
//e[j].val-=d;
//e[j^1].val+=d;
//lv-=d;
//if(h[source]>=n)returncost-lv;
//if(lv==0)break;
//}
//
//if(h[v]<minh)minh=h[v];
//}
//}
//
//if(lv==cost)
//{
//--gap[h[pos]];
//if(gap[h[pos]]==0)h[source]=n;
//h[pos]=minh+1;
//++gap[h[pos]];
//}
//
//returncost-lv;
//
//}
//
//intsap(intst,inted)
//{
//
//source=st;
//sink=ed;
//intret=0;
//memset(gap,0,sizeof(gap));
//memset(h,0,sizeof(h));
//
//gap[st]=n;
//
//while(h[st]<n)
//{
//ret+=dfs(st,INT_MAX);
//}
//
//returnret;
//}
//
//
//intmain()
//{
//#ifndefONLINE_JUDGE
//freopen("in.txt","r",stdin);
//#endif
//intT;
//scanf("%d",&T);
//while(T--)
//{
//scanf("%d%d",&n,&m);
//intx,y;
//intMin=inf,Max=-inf;
//intsrc,des;
//for(inti=1;i<=n;++i)//找出起点src终点des
//{
//scanf("%d%d",&x,&y);
//if(x<=Min)
//{
//src=i;
//Min=x;
//}
//if(x>=Max)
//{
//des=i;
//Max=x;
//}
//}
//
//init();
//intu,v,c;
//for(inti=0;i!=m;++i)
//{
//scanf("%d%d%d",&u,&v,&c);
////addedge(u,v,c);
////addedge(v,u,c);
//insert2(u,v,c);
//}
//
//printf("%d\n",sap(src,des));
//}
//return0;
//}
//邻接表——sha
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
#defineVM10001
#defineEM500100
#definepi3.1415926535897932
#defineabs(x)((x)>0?(x):-(x))
#definesqr(x)((x)*(x))
#definefill(m,v)memset(m,v,sizeof(m))
#defineSS(x)scanf("%d",&x)
#defineinf0x7fffffff
#definehinf0x3f3f3f3f
#definefifirst
#definesesecond
#defineall(x)x.begin(),x.end()
#definerall(v)v.rbegin(),v.rend()
#definesz(v)((int)v.size())
#definey0stupid_cmath
#definey1very_stupid_cmath
#definell__int64
#defineullunsigned__int64
#definepbpush_back
#definempmake_pair
#definerep(i,m)for(inti=0;i<(int)(m);i++)
#definerep2(i,n,m)for(inti=n;i<(int)(m);i++)
#defineFOR(i,a,b)for(inti=(a);i<(b);i++)
#defineFF(i,a)for(inti=0;i<(a);i++)
#defineFFD(i,a)for(inti=(a)-1;i>=0;i--)
#defineCC(m,what)memset(m,what,sizeof(m))
#defineSZ(a)((int)a.size())
#definePP(n,m,a)puts("---");FF(i,n){FF(j,m)cout<<a[i][j]<<'';puts("");}
#definereadfreopen("in.txt","r",stdin)
#definewritefreopen("out.txt","w",stdout)
intdx[]={-1,0,1,0};//upRightdownLeft
intdy[]={0,1,0,-1};
//#defineFor(it,c)for(__typeof(c.begin())it=c.begin();it!=c.end();++it)
usingnamespacestd;
#defineM40010
template<classT>inlinevoidcheckmin(T&a,Tb){if(a==-1||a>b)a=b;}
template<classT>inlinevoidcheckmax(T&a,Tb){if(a<b)a=b;}
intgap[M],dis[M],pre[M],cur[M];
intNE,NV;
inthead[M];
structNode{
intc,pos,next;
}E[999999];
intsap(ints,intt){
memset(dis,0,sizeof(int)*(NV+1));
memset(gap,0,sizeof(int)*(NV+1));
FF(i,NV)cur[i]=head[i];
intu=pre[s]=s,maxflow=0,aug=-1;
gap[0]=NV;
while(dis[s]<NV){
loop:for(int&i=cur[u];i!=-1;i=E[i].next){
intv=E[i].pos;
if(E[i].c&&dis[u]==dis[v]+1){
checkmin(aug,E[i].c);
pre[v]=u;
u=v;
if(v==t){
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u]){
E[cur[u]].c-=aug;
E[cur[u]^1].c+=aug;
}
aug=-1;
}
gotoloop;
}
}
intmindis=NV;
for(inti=head[u];i!=-1;i=E[i].next){
intv=E[i].pos;
if(E[i].c&&mindis>dis[v]){
cur[u]=i;
mindis=dis[v];
}
}
if((--gap[dis[u]])==0)break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
returnmaxflow;
}
voidInsert(intu,intv,intc,intcc=0){
E[NE].c=c;E[NE].pos=v;
E[NE].next=head[u];head[u]=NE++;
E[NE].c=cc;E[NE].pos=u;
E[NE].next=head[v];head[v]=NE++;
}
intmain(){
FF(i,NV)head[i]=-1;
NE=0;
}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
