POJ 1273
给出M条边，N个点，求源点1到汇点N的最大流量。
本文主要就是附上dinic的模板，供以后参考。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h> /*
POJ 1273
dinic算法模板 边是有向的，而且存在重边，且这里重边不是取MAX，而是累加和
*/
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=;
int pri[maxn];
long long sum; //计算总流量
int s,t; //s:源点 t:汇点
int n,m; struct Edge{
int c,f;
}maps[maxn][maxn]; int min(int a,int b){
return a<b?a:b;
}
//每次先BFS，看看是否存在从源点到汇点的增广路
bool BFS() {
queue<int> q;
memset(pri,,sizeof(pri));
pri[]=;
q.push();
while(!q.empty()) {
int temp=q.front();
q.pop();
for(int i=; i<=m; i++) {
if(!pri[i] && maps[temp][i].c-maps[temp][i].f){
pri[i]=pri[temp]+;
if(i==t)
return true; //即如果可以流到汇点，直接return true
q.push(i);
}
}
}
//if(pri[m]>0)
// return true;
return false;
} //p表示当前节点，flow表示该节点通过的流量
int dinic(int p,int flow){
if(p==t){
return flow;
}
int f=flow;
//int value=0;
for(int i=;i<=m;i++){
if(pri[i]==pri[p]+ && maps[p][i].c-maps[p][i].f){
int a=maps[p][i].c-maps[p][i].f; //a为该边可以增加的流量
int ff=dinic(i,min(a,flow)); //ff为路径中所有a的最小值，即为该条路中可以增加的流量
maps[p][i].f+=ff; //正向边
maps[i][p].f-=ff; //逆向边
//value+=ff;
flow-=ff;
if(flow<=)
break; //优化剪枝
}
}
//return value;
if(f-flow<=)
pri[p]=;//如果从p点流出去的流量<=0，那么设置pri[p]的值为0，之后在dinic中就不考虑到p点的情况了。
return f-flow;
}
void init(){
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
maps[i][j].c=maps[i][j].f=;
}
}
}
int main() {
int a,b,c;
s=;
while(scanf("%d%d",&n,&m)!=EOF){
init();
//memset(maps,0,sizeof(maps));
sum=;
t=m;
for(int i=;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
maps[a][b].c+=c; //该题有重边，这里要+=，不是去max
}
while(BFS()){
sum+=dinic(s,INF);
}
printf("%I64d\n",sum);
}
return ;
}
再给出一个大牛的模板：
#include <cstdio>
#include <queue> using namespace std; typedef int LL;
const int N = ;
const int M = N << ;
const int INF = (int)1e9; struct Dinic { struct Edge {
int v;
LL cap, flow;
Edge* next, * pair; void init(int a, LL b, Edge* e1, Edge* e2) {
v = a, cap = b, flow = , next = e1, pair = e2;
}
}; Edge* head[N], * used[N];
Edge* it;
int lev[N], que[N];
Edge E[M];
int n, s, t;
LL maxFlow; void init(int n, int s, int t) {
it = E;
this->n = n;
this->s = s, this->t = t;
for (int i = ; i < n; i++)
head[i] = ;
} void add(int u, int v, LL c) {
it->init(v, c, head[u], it + );
head[u] = it++;
it->init(u, , head[v], it - );
head[v] = it++;
} bool bfs() {
for (int i = ; i < n; lev[i++] = -);
lev[s] = ;
int st = , ed = ;
que[ed++] = s;
while (st < ed) {
int u = que[st++];
for (Edge* e = head[u]; e; e = e->next) {
int v = e->v;
if (lev[v] == - && e->cap > e->flow) {
lev[v] = lev[u] + ;
que[ed++] = v;
}
}
}
return lev[t] != -;
} LL dfs(int u, LL f) {
if (u == t) return f;
for (Edge* & e = used[u]; e; e = e->next) {
int v = e->v;
if (e->cap > e->flow && lev[v] == lev[u] + ) {
LL tmp = dfs(v, min(e->cap - e->flow, f));
if (tmp > ) {
e->flow += tmp;
e->pair->flow -= tmp;
return tmp;
}
}
}
return ;
} void run() {
maxFlow = ;
while (bfs()) {
for (int i = ; i < n; i++)
used[i] = head[i];
LL f = ;
while (f) {
f = dfs(s, INF);
maxFlow += f;
}
}
} }G; int main() {
int n, m, u, v, w;
while (~scanf("%d%d", &m, &n)) {
G.init(n, , n - );
while (m--) {
scanf("%d%d%d", &u, &v, &w);
G.add(u - , v - , w);
}
G.run();
printf("%d\n", G.maxFlow);
}
return ;
}