上学路线(递归sap-不完全) - c++编程基础

nt[++d2[u]]++;
return tot;
}
int main()
{
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
memset(pre,0,sizeof(pre));
scanf("%d%d",&n,&m);
For(i,m)
{
int u,v,w1,w2;
scanf("%d%d%d%d",&u,&v,&w1,&w2);
addedge(u,v,w1,w2);
addedge(v,u,w1,w2);
}
spfa();
// for (int i=1;i<=n;i++) cout< cout< int ans=0;
spfa2();
int de_bug_1=0;
For(i,n)
Forp(p,i)
{
if (d[i]>d[edge[p]]) c[p]=0;
//*0
// if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout< if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout< }
// cout< b[0]=1;
For(i,n)
Forp(p,i)
{
while (next[p]&&!b[next[p]]) next[p]=next[next[p]];
}

while(/*sap_T*/1)
{
if (d2[1]>=n) break;
int w=sap(1,INF);
// if (!w) break;
// cout< ans+=w;
}
cout< return 0;
}

#include
#include
#include
#include
#include
#include
#define MAXN (500+10)
#define MAXM (124750+10)
#define MAXCi (10000+10)
#define INF (2139062143)
#define For(i,n) for(int i=1;i<=n;i++)
#define Forp(p,u) for (int p=pre[u];p;p=next[p])
using namespace std;
int n,m,edge[2*MAXM],weight[2*MAXM],c[2*MAXM],next[2*MAXM],pre[MAXN],size=1;
void addedge(int u,int v,int w,int w2)
{
edge[++size]=v;
weight[size]=w;
c[size]=w2;
next[size]=pre[u];
pre[u]=size;
}
int d[MAXN],q[MAXN*8];
void spfa()
{
memset(d,127,sizeof(d));
d[1]=0;
int head=1,tail=1;q[1]=1;
while (head<=tail)
{
int &u=q[head];
Forp(p,u)
{
int &v=edge[p];
if (d[v]==INF||d[u]+weight[p] {
q[++tail]=v;d[v]=d[u]+weight[p];
}
}
head++;
}
}

int d2[MAXN],cnt[MAXN];
void spfa2()
{
memset(d2,127,sizeof(d2));
memset(cnt,0,sizeof(cnt));
d2[n]=0;cnt[0]=1;
int head=1,tail=1;q[1]=n;
while (head<=tail)
{
int &u=q[head];
Forp(p,u)
{
int &v=edge[p];
if (d[u]-weight[p]!=d[v]) continue;
if (d2[v]==INF)
{
q[++tail]=v;d2[v]=d2[u]+1;
cnt[d2[v]]++;
}
}
head++;
}
}
bool sap_T=1,b[2*MAXM]={0};
int sap(int u,int flow)
{
if (u==n) return flow;
int tot=0,minj=INF;
Forp(p,u)
{
int &v=edge[p];
/*
if (d2[v]==INF) continue;
if (!(d[u]+weight[p]==d[v]||d[u]-weight[p]==d[v])) continue;
*/
if (!b[p]) continue;
if (c[p]>0&&d2[u]==d2[v]+1)
{
int w=sap(v,min(flow-tot,c[p]));
c[p]-=w;c[p^1]+=w;tot+=w;
if (flow==tot) return tot;
}else if (c[p]) minj=min(minj,d2[v]);
}
if (--cnt[d2[u]]==0)
{
d2[1]=n,sap_T=0;/*return tot;*/
}//d2[1]=n+1;
// if (minj^INF) cnt[d2[u]=minj+1]++;
/* else*/ cnt[++d2[u]]++;
return tot;
}
int main()
{
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
memset(pre,0,sizeof(pre));
scanf("%d%d",&n,&m);
For(i,m)
{
int u,v,w1,w2;
scanf("%d%d%d%d",&u,&v,&w1,&w2);
addedge(u,v,w1,w2);
addedge(v,u,w1,w2);
}
spfa();
// for (int i=1;i<=n;i++) cout< cout< int ans=0;
spfa2();
int de_bug_1=0;
For(i,n)
Forp(p,i)
{
if (d[i]>d[edge[p]]) c[p]=0;
//*0
// if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout< if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout< }
// cout< b[0]=1;
For(i,n)
Forp(p,i)
{
while (next[p]&&!b[next[p]]) next[p]=next[next[p]];
}

while(/*sap_T*/1)
{
if (d2[1]>=n) break;
int w=sap(1,INF);
// if (!w) br

上学路线(递归sap-不完全) (二)