2013-team4/code/network-flow
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
Dinic 最大流
FL 为流量类型，可以修改，MAXN 为最大点数
}}}
{{{
创建
Dinic D;
清除全图
D.clear_graph();
清除图中流量
D.clear_flow();
从 from 到 to 添加一条容量为 cap 的边
D.add_edge(from, to, cap);
从 s 到 t 计算最大流
D.max_flow(s, t);
}}}
{{{
typedef long long FL;
const int MAXN = 20005;
const FL INF = 2100000000;
struct Edge{
int from, to;
FL cap, flow;
Edge(int fr, int t, FL c, FL fl){
from = fr; to = t; cap = c; flow = fl;
}
};
struct Dinic{
vector<int> G[MAXN];
vector<Edge> E;
int s, t;
int cur[MAXN], d[MAXN];
void clear_graph(){
E.clear();
for(int i = 0; i < MAXN; i++)
G[i].clear();
}
void clear_flow(){
for(int i = 0; i < E.size(); i++)
E[i].flow = 0;
}
void add_edge(int from, int to, FL cap){
int m = E.size();
E.push_back(Edge(from, to, cap, 0));
E.push_back(Edge(to, from, 0, 0));
G[from].push_back(m);
G[to].push_back(m + 1);
}
bool bfs(){
bool vis[MAXN];
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s); d[s] = 0; vis[s] = 1;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0; i < G[x].size(); i++){
Edge &e = E[G[x][i]];
if(vis[e.to] == 0 && e.cap > e.flow){
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
FL dfs(int x, FL mi){
if(x == t || mi == 0) return mi;
FL sum = 0;
for(int &i = cur[x]; i < G[x].size(); i++){
Edge &e = E[G[x][i]];
if(d[x] + 1 == d[e.to]){
FL f = dfs(e.to, min(mi, e.cap - e.flow));
if(f > 0){
e.flow += f;
E[G[x][i] ^ 1].flow -= f;
sum += f;
mi -= f;
if(mi == 0) break;
}
}
}
return sum;
}
FL max_flow(int s, int t){
this->s = s; this->t = t;
FL flow = 0;
while(bfs()){
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
};
}}}
{{{
//网络流模板dinic+sap by zimpha
//经过POJ 3469测试
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=20010;
const int MAXM=600000;
const int inf=1000000000;
struct Edge {
int v, flow;
Edge *next, *op;
}mem[MAXM];
Edge *E[MAXN], *cur[MAXN], *cnt;
int pre[MAXN], dis[MAXN], gap[MAXN];
int N, M, S, T, NN;
inline void addedge(int u, int v, int a, int b) {
cnt->v=v; cnt->flow=a; cnt->next=E[u]; E[u]=cnt++;
cnt->v=u; cnt->flow=b; cnt->next=E[v]; E[v]=cnt++;
E[u]->op=E[v]; E[v]->op=E[u];
}
int sap() {
int maxflow=0, aug=inf, u, v;
for (int i=0; i<NN; i++) cur[i]=E[i], gap[i]=dis[i]=0;
gap[S]=NN; u=pre[S]=S;
while (dis[S]<NN) {
bool flag=false;
for (Edge *&p=cur[u]; p; p=p->next)
if (p->flow>0 && dis[u]==dis[v=p->v]+1) {
flag=true;
if (p->flow<aug) aug=p->flow;
pre[v]=u; u=v;
if (u==T) {
maxflow+=aug;
while (u!=S) {
u=pre[u];
cur[u]->flow-=aug;
cur[u]->op->flow+=aug;
}
aug=inf;
}
break;
}
if (flag) continue;
int mindis=NN;
for (Edge *p=E[u]; p; p=p->next)
if (p->flow>0 && dis[p->v]<mindis) {
mindis=dis[p->v]; cur[u]=p;
}
if ((--gap[dis[u]])==0) break;
gap[dis[u]=mindis+1]++; u=pre[u];
}
return maxflow;
}
int level[MAXN], Q[MAXN];
bool dinic_bfs() {
memset(level, -1, sizeof(level));
level[S]=0; Q[0]=S;
for (int h=0, t=1; h<t; h++) {
int u=Q[h], v;
for (Edge *p=E[u]; p; p=p->next)
if (level[v=p->v]==-1 && p->flow>0) {
level[v]=level[u]+1;
Q[t++]=v;
}
}
return (level[T]!=-1);
}
int dinic_dfs(int u, int low) {
if (u==T) return low;
int ret=0, tmp, v;
for (Edge *p=E[u]; p && ret<low; p=p->next)
if (level[v=p->v]==level[u]+1 && p->flow>0) {
if (tmp=dinic_dfs(v, min(low-ret, p->flow))) {
ret+=tmp, p->flow-=tmp, p->op->flow+=tmp;
}
}
if (!ret) level[u]=-1; return ret;
}
int dinic() {
int maxflow=0, t;
while (dinic_bfs()) {
while (t=dinic_dfs(S, inf)) maxflow+=t;
}
return maxflow;
}
void init() {
memset(E, 0, sizeof(E));
S=0; T=N+1; NN=N+2; cnt=mem;
}
int main() {
init();
return 0;
}
}}}Dinic 最大流
FL 为流量类型，可以修改，MAXN 为最大点数
创建
Dinic D;
清除全图
D.clear_graph();
清除图中流量
D.clear_flow();
从 from 到 to 添加一条容量为 cap 的边
D.add_edge(from, to, cap);
从 s 到 t 计算最大流
D.max_flow(s, t);
typedef long long FL;
const int MAXN = 20005;
const FL INF = 2100000000;
struct Edge{
int from, to;
FL cap, flow;
Edge(int fr, int t, FL c, FL fl){
from = fr; to = t; cap = c; flow = fl;
}
};
struct Dinic{
vector<int> G[MAXN];
vector<Edge> E;
int s, t;
int cur[MAXN], d[MAXN];
void clear_graph(){
E.clear();
for(int i = 0; i < MAXN; i++)
G[i].clear();
}
void clear_flow(){
for(int i = 0; i < E.size(); i++)
E[i].flow = 0;
}
void add_edge(int from, int to, FL cap){
int m = E.size();
E.push_back(Edge(from, to, cap, 0));
E.push_back(Edge(to, from, 0, 0));
G[from].push_back(m);
G[to].push_back(m + 1);
}
bool bfs(){
bool vis[MAXN];
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s); d[s] = 0; vis[s] = 1;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0; i < G[x].size(); i++){
Edge &e = E[G[x][i]];
if(vis[e.to] == 0 && e.cap > e.flow){
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
FL dfs(int x, FL mi){
if(x == t || mi == 0) return mi;
FL sum = 0;
for(int &i = cur[x]; i < G[x].size(); i++){
Edge &e = E[G[x][i]];
if(d[x] + 1 == d[e.to]){
FL f = dfs(e.to, min(mi, e.cap - e.flow));
if(f > 0){
e.flow += f;
E[G[x][i] ^ 1].flow -= f;
sum += f;
mi -= f;
if(mi == 0) break;
}
}
}
return sum;
}
FL max_flow(int s, int t){
this->s = s; this->t = t;
FL flow = 0;
while(bfs()){
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
};
//网络流模板dinic+sap by zimpha
//经过POJ 3469测试
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=20010;
const int MAXM=600000;
const int inf=1000000000;
struct Edge {
int v, flow;
Edge *next, *op;
}mem[MAXM];
Edge *E[MAXN], *cur[MAXN], *cnt;
int pre[MAXN], dis[MAXN], gap[MAXN];
int N, M, S, T, NN;
inline void addedge(int u, int v, int a, int b) {
cnt->v=v; cnt->flow=a; cnt->next=E[u]; E[u]=cnt++;
cnt->v=u; cnt->flow=b; cnt->next=E[v]; E[v]=cnt++;
E[u]->op=E[v]; E[v]->op=E[u];
}
int sap() {
int maxflow=0, aug=inf, u, v;
for (int i=0; i<NN; i++) cur[i]=E[i], gap[i]=dis[i]=0;
gap[S]=NN; u=pre[S]=S;
while (dis[S]<NN) {
bool flag=false;
for (Edge *&p=cur[u]; p; p=p->next)
if (p->flow>0 && dis[u]==dis[v=p->v]+1) {
flag=true;
if (p->flow<aug) aug=p->flow;
pre[v]=u; u=v;
if (u==T) {
maxflow+=aug;
while (u!=S) {
u=pre[u];
cur[u]->flow-=aug;
cur[u]->op->flow+=aug;
}
aug=inf;
}
break;
}
if (flag) continue;
int mindis=NN;
for (Edge *p=E[u]; p; p=p->next)
if (p->flow>0 && dis[p->v]<mindis) {
mindis=dis[p->v]; cur[u]=p;
}
if ((--gap[dis[u]])==0) break;
gap[dis[u]=mindis+1]++; u=pre[u];
}
return maxflow;
}
int level[MAXN], Q[MAXN];
bool dinic_bfs() {
memset(level, -1, sizeof(level));
level[S]=0; Q[0]=S;
for (int h=0, t=1; h<t; h++) {
int u=Q[h], v;
for (Edge *p=E[u]; p; p=p->next)
if (level[v=p->v]==-1 && p->flow>0) {
level[v]=level[u]+1;
Q[t++]=v;
}
}
return (level[T]!=-1);
}
int dinic_dfs(int u, int low) {
if (u==T) return low;
int ret=0, tmp, v;
for (Edge *p=E[u]; p && ret<low; p=p->next)
if (level[v=p->v]==level[u]+1 && p->flow>0) {
if (tmp=dinic_dfs(v, min(low-ret, p->flow))) {
ret+=tmp, p->flow-=tmp, p->op->flow+=tmp;
}
}
if (!ret) level[u]=-1; return ret;
}
int dinic() {
int maxflow=0, t;
while (dinic_bfs()) {
while (t=dinic_dfs(S, inf)) maxflow+=t;
}
return maxflow;
}
void init() {
memset(E, 0, sizeof(E));
S=0; T=N+1; NN=N+2; cnt=mem;
}
int main() {
init();
return 0;
}