网络最大流（SAP）
#include <iostream>#include <cstring>
using namespace std;
#define maxn 40010
#define maxm 99999
#define Type int
struct Graph {
int gap[maxn], pre[maxn], cur[maxn], dis[maxn];
int NE, NV;
int head[maxn];
int from[maxn];
// int flow_in_point[maxn];
struct Node{
int pos,next;
Type c;
}E[maxm];
template<class T> inline void checkmin(T &a,const T &b) {if(a < 0 || a > b)a = b;}
Type sap(int s,int t) {
memset(dis,0,sizeof(dis[0])*NV);
memset(gap,0,sizeof(gap[0])*NV);
// memset(flow_in_point, 0, sizeof(flow_in_point));
for(int i = 0 ; i < NV ; i ++) cur[i] = head[i];
int u = pre[s] = s;
Type maxflow = 0,aug = -1;
gap[0] = NV;
while(dis[s] < NV) {
loop: for(int &i = cur[u]; i != -1; i = E[i].next) {
int v = E[i].pos;
if(E[i].c && dis[u] == dis[v] + 1) {
checkmin(aug , E[i].c);
pre[v] = u;
u = v;
if(v == t) {
maxflow += aug;
for(u = pre[u];v != s;v = u,u = pre[u]) {
// if(pre[v] == from[v])
// flow_in_point[v] += aug;
// else
// flow_in_point[v] -= aug;
E[cur[u]].c -= aug;
E[cur[u]^1].c += aug;
}
aug = -1;
}
goto loop;
}
}
int mindis = NV;
for(int i = head[u]; i != -1 ; i = E[i].next) {
int v = E[i].pos;
if(E[i].c && mindis > dis[v]) {
cur[u] = i;
mindis = dis[v];
}
}
if( (--gap[dis[u]]) == 0) break;
gap[ dis[u] = mindis+1 ] ++;
u = pre[u];
}
return maxflow;
} www.zzzyk.com
void Insert(int u,int v,Type c,Type cc = 0) {
E[NE].c = c; E[NE].pos = v;
E[NE].next = head[u]; head[u] = NE++;
E[NE].c = cc; E[NE].pos = u;
E[NE].next = head[v]; head[v] = NE++;
}
void init(int n) {
NV = n;
for(int i = 0 ; i < NV ; i ++) head[i] = -1;
NE = 0;
}
}G;
补充：综合编程 , 其他综合 ,
