题目抽象：给你m条边u,v,c。 n个定点，源点1，汇点n.求最大流。 最好的入门题，各种算法都可以拿来练习
（1）： 一般增广路算法 ford()
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x4fffffff;
const double EXP = 1e-;
const int MS = ;
const int SIZE = ; struct edge
{
int c, f;
}edges[MS][MS]; int n, m; int flag[MS];
int pre[MS];
int alpha[MS]; int que[SIZE]; int u;
int qs, qe;
int i, j; void ford()
{
while ()
{
// label method
memset(flag, 0xff, sizeof(flag));
memset(pre, 0xff, sizeof(pre));
memset(alpha, 0xff, sizeof(alpha));
flag[] = ;
pre[] = ;
alpha[] = INF;
qs = qe = ;
que[qe++] = ; while (qs < qe&&flag[n ] == -)
{
u = que[qs++];
for (int i = ; i <= n; i++)
{
if (flag[i] == -)
{
if (edges[u][i].c >&&edges[u][i].f < edges[u][i].c)
{
flag[i] = ; pre[i] = u;
alpha[i] = min(alpha[u], edges[u][i].c - edges[u][i].f);
que[qe++] = i;
}
else if (edges[i][u].c>&&edges[i][u].f>)
{
flag[i] = ; pre[i] = -u;
alpha[i] = min(alpha[u], edges[i][u].f);
que[qe++] = i;
}
}
}
flag[u] = ;
} // END OF WHILE
if (flag[n ] == - || alpha[n ] == )
break; // END OF WHILE int k1 = n , k2 = abs(pre[k1]);
int a = alpha[n ];
while ()
{
if (edges[k2][k1].c>) //用f是否==INF来判断正向
edges[k2][k1].f += a;
else
edges[k1][k2].f -= a;
if (k2 == )
break;
k1 = k2;
k2 = abs(pre[k1]);
} // END OF WHILE
} // END OF WHILE int max_flow = ;
for (int i = ; i <=n; i++)
{
for (int j = ; j <=n; j++)
{
if (i == && edges[i][j].f >)
max_flow += edges[i][j].f;
// if (edges[i][j].f > 0)
// printf("%d-->%d: %d\n", i, j, edges[i][j].f);
}
}
printf("%d\n", max_flow);
} int main()
{
int u, v, c, f;
while(scanf("%d%d",&m,&n)!=EOF)
{
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
// edges[i][j].c = edges[i][j].f = INF;
edges[i][j].c=edges[i][j].f=;
for (int i = ; i < m; i++)
{
//scanf("%d%d%d%d", &u, &v, &c, &f);
scanf("%d%d%d",&u,&v,&c); // 这里是零流
edges[u][v].c +=c; // 可能有重边
// edges[u][v].f = f;
}
ford();
}
return ;
}
(2): dinic()
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <iomanip>
#include <cstdlib>
#include <sstream>
using namespace std;
typedef long long LL;
const int INF=0x5fffffff;
const double EXP=1e-;
const int MS=; int edges[MS][MS];
int level[MS];
int que[MS],qs,qe;
int n,m,ans; int BFS() // BFS求level
{
memset(level,0xff,sizeof(level));
level[]=;
qs=qe=;
que[qe++]=;
while(qs<qe)
{
int u=que[qs++];
for(int v=;v<=n;v++)
{
if(level[v]<&&edges[u][v]>)
{
level[v]=level[u]+;
que[qe++]=v;
}
}
}
if(level[n]>) // 汇点在残留网络中，存在增广路
return ;
else
return ;
} int DFS(int u,int minv)
{
if(u==n)
return minv;
int t;
for(int v=;v<=n;v++)
if(edges[u][v]>&&level[v]==level[u]+&&(t=DFS(v,min(minv,edges[u][v]))))
{
edges[u][v]-=t;
edges[v][u]+=t;
return t;
}
return ;
} int main()
{
int u,v,c;
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(edges,,sizeof(edges));
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
edges[u][v]+=c;
}
ans=;
int t;
// DINIC()
while(BFS()) //还存在增广路
{
while(t=DFS(,INF)) //DFS找出残留网络中的所有增广路
{
ans+=t;
}
}
printf("%d\n",ans);
}
return ;
}