#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue> using namespace std;
const int INF=;
const int maxn=,maxm=;
int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn]; void addedge(int a,int b,int c)
{
nxt[++cnt]=fir[a];
to[cnt]=b;
cap[cnt]=c;
fir[a]=cnt;
} bool BFS(int S,int T)
{
memset(dis,,sizeof(dis));
dis[T]=;
queue<int>q;q.push(T);
while(!q.empty())
{
int node=q.front();q.pop();
for(int i=fir[node];i;i=nxt[i])
{
if(dis[to[i]])continue;
dis[to[i]]=dis[node]+;
q.push(to[i]);
}
}
return dis[S];
}
int fron[maxn];
int ISAP(int S,int T)
{
if(!BFS(S,T))
return ;
for(int i=;i<=T;i++)++gap[dis[i]];
int p=S,ret=;
memcpy(fron,fir,sizeof(fir));
while(dis[S]<=T)
{
if(p==T){
int f=INF;
while(p!=S){
f=min(f,cap[path[p]]);
p=to[path[p]^];
}
p=T;ret+=f;
while(p!=S){
cap[path[p]]-=f;
cap[path[p]^]+=f;
p=to[path[p]^];
}
}
int &ii=fron[p];
for(;ii;ii=nxt[ii]){
if(!cap[ii]||dis[to[ii]]+!=dis[p])
continue;
else
break;
} if(ii){
p=to[ii];
path[p]=ii;
} else{
if(--gap[dis[p]]==)break;
int minn=T+;
for(int i=fir[p];i;i=nxt[i])
if(cap[i])
minn=min(minn,dis[to[i]]);
gap[dis[p]=minn+]++;
fron[p]=fir[p];
if(p!=S)
p=to[path[p]^];
}
}
return ret;
} void Init()
{
memset(fir,,sizeof(fir));
memset(gap,,sizeof(gap));
cnt=;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
Init();
for(int i=;i<=m;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
addedge(y,x,);
}
printf("%d\n",ISAP(,n));
} return ;
}
后来又打了一遍，代码风格都变了。（这个没有多组数据）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=;
const int maxn=;
const int maxm=;
int cnt=,fir[maxn],to[maxm],nxt[maxm],cap[maxm];
void addedge(int a,int b,int c){
nxt[++cnt]=fir[a];
fir[a]=cnt;
cap[cnt]=c;
to[cnt]=b;
} queue<int>q;
int dis[maxn];
bool BFS(int s,int t){
dis[t]=;q.push(t);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=fir[x];i;i=nxt[i])
if(!dis[to[i]]){
dis[to[i]]=dis[x]+;
q.push(to[i]);
}
}
return dis[s];
} int fron[maxn];
int gap[maxn],path[maxn];
int ISAP(int s,int t){
if(!BFS(s,t))return ;
for(int i=s;i<=t;i++)++gap[dis[i]];
for(int i=s;i<=t;i++)fron[i]=fir[i];
int p=s,ret=,f;
while(dis[s]<=t){
if(p==t){
f=INF;
while(p!=s){
f=min(f,cap[path[p]]);
p=to[path[p]^];
}
ret+=f;p=t;
while(p!=s){
cap[path[p]]-=f;
cap[path[p]^]+=f;
p=to[path[p]^];
}
}
int &ii=fron[p];
for(;ii;ii=nxt[ii])
if(cap[ii]&&dis[p]==dis[to[ii]]+)
break;
if(ii)
path[p=to[ii]]=ii;
else{
if(--gap[dis[p]]==)break;
int minn=t+;
for(int i=fir[p];i;i=nxt[i])
if(cap[i])minn=min(minn,dis[to[i]]);
++gap[dis[p]=minn+];ii=fir[p];
if(p!=s)p=to[path[p]^];
}
}
return ret;
} int main(){
int n,m;
scanf("%d%d",&m,&n);
for(int i=,a,b,c;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,);
}
printf("%d\n",ISAP(,n));
return ;
}
又打一遍，很好看的结构体。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=;
const int maxm=;
const int INF=;
int cnt,tot,fir[maxn],fron[maxn],dis[maxn];
int to[maxm],nxt[maxm],gap[maxn],path[maxn];
int cap[maxm];queue<int>q; struct Max_Flow{
void Init(int tot_=){
tot=tot_;cnt=;
memset(fir,,sizeof(fir));
memset(dis,,sizeof(dis));
memset(gap,,sizeof(gap));
} void add(int a,int b,int c){
nxt[++cnt]=fir[a];
fir[a]=cnt;
cap[cnt]=c;
to[cnt]=b;
} void addedge(int a,int b,int c){
add(a,b,c);
add(b,a,);
} bool BFS(int s,int t){
dis[t]=;q.push(t);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=fir[x];i;i=nxt[i])
if(!dis[to[i]]){
dis[to[i]]=dis[x]+;
q.push(to[i]);
}
}
return dis[s];
} int Aug(int s,int t,int &p){
int f=INF;
while(p!=s){
f=min(f,cap[path[p]]);
p=to[path[p]^];
}p=t;
while(p!=s){
cap[path[p]]-=f;
cap[path[p]^]+=f;
p=to[path[p]^];
}
return f;
} int ISAP(int s,int t){
if(!BFS(s,t))return ;
for(int i=s;i<=t;i++)fron[i]=fir[i];
for(int i=s;i<=t;i++)gap[dis[i]]+=;
int p=s,ret=;
while(dis[s]<=tot){
if(p==t)ret+=Aug(s,t,p); for(int &i=fron[p];i;i=nxt[i])
if(cap[i]&&dis[p]==dis[to[i]]+){
path[p=to[i]]=i;
break;
} if(!fron[p]){
if(--gap[dis[p]]==)
break;
int Min=tot;
for(int i=fir[p];i;i=nxt[i])
if(cap[i])Min=min(Min,dis[to[i]]);
gap[dis[p]=Min+]+=;fron[p]=fir[p];
if(p!=s)p=to[path[p]^];
}
}
return ret;
}
}isap;