HDU 4280 Island Transport 又一发SAP

红色多瑙河

　　终于有点SAP的感觉了。总结下模板



#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100008;
const int INF=0x7f7f7f7f;
struct fuck{
int u,v,w,cap,next;
}edge[maxn<<2];
int head[maxn];
int tol;
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol].cap=w;
edge[tol].next=head;
head=tol++;
edge[tol].u=v;
edge[tol].v=u;
edge[tol].cap=0;
edge[tol].next=head[v];
head[v]=tol++;
}
bool vis[maxn];
int dep[maxn],gap[maxn];
//  bfs反向构造层次图，那么只关注反向残量为0的边
void bfs(int sour,int sink)
{
queue<int>  q;
memset(vis,false,sizeof(vis));
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
q.push(sink);
dep[sink]=0;gap[0]=1;vis[sink]=true;
int u,v,i;
while(!q.empty())
{
u=q.front();q.pop();
for(i=head;i!=-1;i=edge.next)
{
v=edge.v;
if(!vis[v]&&edge.cap==0)
{
vis[v]=true;
dep[v]=dep+1;
q.push(v);
gap[dep[v]]++;
}
}
}
}
int cur[maxn],S[maxn];
int last;
// 分三个过程
int sap(int sour,int sink)
{
bfs(sour,sink);
int i,u;
for(i=0;i<=last;i++)
cur=head;//当前狐
int top=0,max_flow=0;
u=sour;
/*三个步骤。1从当前狐查找可行狐（残量大于0，层次差为1）
2 若没有找到可行狐，寻找当前节点的所有相邻点，找最小的dep修改当前点层次
退回到上一个点继续查找
3 若找到汇点，在路径中找到一条残量最小的边，以这个残量修改整个路径
然后从这条边的起点继续查找*/
while(dep[sour]<last)//起点层次等于所有弧长说明没有***了
    {
if(u==sink)
{
int temp=INF,inser;
for(i=0;i<top;i++)
{
if(edge[S].cap<temp)
{
temp=edge[S].cap;
inser=i;
}
}
for(i=0;i<top;i++)
{
edge[S].cap-=temp;
edge[S^1].cap+=temp;
}
max_flow+=temp;
top=inser;
u=edge[S[top]].u;
}
if(u!=sink&&gap[dep-1]==0)   break;//简直，出现断层即退出
for(i=cur;i!=-1;i=edge.next)
if(edge.cap>0&&dep==dep[edge.v]+1)
break;
if(i!=-1)
{
cur=i;
S[top++]=i;
u=edge.v;
}
else
{
int mi=last;
for(i=head;i!=-1;i=edge.next)
{
if(edge.cap==0)  continue;
if(mi>dep[edge.v])
{
mi=dep[edge.v];
cur=i;
}
}
--gap[dep];
dep=mi+1;
++gap[dep];
if(u!=sour)     u=edge[S[--top]].u;
}
}
return max_flow;
}
int main()
{
int i,j,n,m,u,v,w,t,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
int sour,sink;
int mi=1e9,ma=-1e9;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(x<mi)
{
mi=x;
sour=i;
}
if(x>ma)
{
ma=x;
sink=i;
}
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
last=n;
printf("%d\n",sap(sour,sink));
}
return 0;
}