理论：
#include#include #include #include using namespace std;#define N 5001#define M 50001const int inf=1e9;int n,m,src,decc;int tot=1;int front[N],to[M<<1],nxt[M<<1],from[M<<1];int val[M<<1],cap[M<<1];int max_flow,cost;int dis[N];bool vis[N];void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v,int w,int f){ to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=f; cap[tot]=w; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=-f; cap[tot]=0;}int augment(int now,int flow){ vis[now]=true; if(now==decc) { cost+=-dis[src]*flow; max_flow+=flow; return flow; } int delta; for(int i=front[now];i;i=nxt[i]) { if(cap[i] && !vis[to[i]] && dis[to[i]]==dis[now]+val[i]) { delta=augment(to[i],min(flow,cap[i])); if(delta) { cap[i]-=delta; cap[i^1]+=delta; return delta; } } } return 0;}bool retreat(){ if(vis[decc]) return true; int mi=inf; for(int i=2;i<=tot;i++) { if(cap[i] && vis[from[i]] && !vis[to[i]]) mi=min(mi,dis[from[i]]+val[i]-dis[to[i]]); } if(mi==inf) return false; for(int i=1;i<=n;++i) if(vis[i]) dis[i]-=mi; return true;}void zkw(){ do { memset(vis,false,sizeof(vis)); augment(src,inf); }while(retreat()); cout< <<' '<