RT,爆空间了,目前看来是爆队列或者爆栈的问题,求查错。
网络流代码:
bool get_dep()
{
memset(dep,0,sizeof(dep));
q.push(1);
dep[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=1;v<=totn;v++)
{
if(dep[v]||!G[u][v])
{
continue;
}
dep[v]=dep[u]+1;
q.push(v);
}
}
return dep[2]!=0;
}
int get_del(int u,int flow)
{
if(u==2||!flow)
{
return flow;
}
int max_flow=0;
for(int &v=cur[u];v<=totn;v++)
{
if(dep[u]+1!=dep[v]&&!G[u][v])
{
continue;
}
int del_flow=get_del(v,min(flow,G[u][v]));
if(del_flow)
{
G[u][v]-=del_flow;
G[v][u]+=del_flow;
max_flow+=del_flow;
flow-=del_flow;
if(!flow)
{
break;
}
}
else
{
dep[v]=0;
}
}
return max_flow;
}
int Dinic()
{
int max_flow=0;
while(get_dep())
{
memset(cur,0,sizeof(cur));
int flow;
while(flow=get_del(1,1e9))
{
max_flow+=flow;
}
}
return max_flow;
}