链接：http://poj.org/problem?id=1273
题意：农夫的农场被水淹了，他建了一些排水沟来排水，最终把这些水排到小河里，现有n个点，节点1~n-1为池塘，水从1开始流，n为小河。然后有m条排水沟，每条排水沟告诉起点、终点、最大水流速度，现在求这个排水系统的最大排水速度。
网络最大流裸题
dinic模板
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson r,m+1,rt<<1|1
struct node{
int u,w,next;
}edge[5000];
int head[2100],vis[2100],dist[2100];
int n,m,src,sink,cnt;
void add_edge(int a,int b,int c){
edge[cnt].u = b;
edge[cnt].w = c;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void bfs(){
int i, j;
memset(dist,0,sizeof(dist));
queue<int>q;
vis[src] = 1;
q.push(src);
while(!q.empty()){
int u = q.front();
q.pop();
for(i=head[u];i!=-1;i=edge[i].next){
if(!vis[edge[i].u]&&edge[i].w){
q.push(edge[i].u);
dist[edge[i].u] = dist[u] + 1;
vis[edge[i].u] = 1;
}
}
}
}
int dfs(int u,int delta){
int i,j;
if(u==sink) return delta;
else{
int ret = 0;
for(i=head[u];i!=-1&δi=edge[i].next){
if(edge[i].w&&dist[edge[i].u]==dist[u]+1){
int dd = dfs(edge[i].u,min(edge[i].w,delta));
edge[i].w -= dd;
edge[i^1].w += dd;
delta -= dd;
ret += dd;
}
}
return ret;
}
}
int maxflow(){
int ret = 0;
while(1){
memset(vis,0,sizeof(vis));
bfs();
if(!vis[sink]) break;
ret += dfs(src,INF);
}
return ret;
}
int main(){
int i,j;
int a,b,x;
while(scanf("%d%d",&m,&n)!=EOF){
memset(head,-1,sizeof(head));
int cnt = 0;
src = 1;
sink = n;
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&x);
add_edge(a,b,x);
add_edge(b,a,0);
}
int ans = maxflow();
printf("%d\n",ans);
}
return 0;
}
isap模板
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 500100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct Edge{
int u, v, weight;
int next;
}edge[5000];
int head[220],cur[220],dist[220],Count[220],augment[220],parent[220];
/*
*寻找增广路径的过程中, cur[u]保存的是对于顶点u当前遍历的边, 寻找顶点u的邻接边时不用每次
都从head[u]开始找, 而是从cur[u]开始找, 这样就减少了搜索次数
*Count[l]表示对于属于层次l的顶点个数, 如果某个层次没有顶点了,
就出现断层, 意味着没有增广路径了, 这就是gap优化, 可以提前结束寻找过程
*augment[v]表示从源点到顶点v中允许的最大流量, 即这条路线的最小权重
*/
int n,m,cnt;
void add_edge(int a, int b, int c)
{
edge[cnt].u = a;
edge[cnt].v = b;
edge[cnt].weight = c;
edge[cnt].next = head[a];
head[a] = cnt++;
}
int isap(int s, int e)
{
int i, u, v, max_flow, aug, min_lev;
memset(dist,0,sizeof(dist));
memset(Count,0,sizeof(Count));
for (i=0;i<=n;i++){
cur[i] = head[i];
}
max_flow = 0;
augment[s] = INF;
parent[s] = -1;
u = s;
while(dist[s]<n){ /* 不能写成level[s] < INF */
if(u==e){ /* 找到一条增广路径 */
max_flow += augment[e];
aug = augment[e];
for(v=parent[e];v!=-1;v=parent[v]){ /* 从后往前遍历路径 */
i = cur[v];
edge[i].weight -= aug;
edge[i^1].weight += aug;
augment[edge[i].v] -= aug;
if (edge[i].weight == 0) u = v; /* u指向增广后最后可达的顶点, 下次就从它继续找 */
}
}
/* 从顶点u往下找邻接点 */
for(i=cur[u];i!=-1;i=edge[i].next) { /* 从cur[u]开始找, 而不是head[u]从头开始, cur[u]保存的是上次找过的边 */
v = edge[i].v;
if(edge[i].weight>0&&dist[u]==(dist[v]+1)){ /* 找到一条边就停止 */
augment[v] = min(augment[u],edge[i].weight);
cur[u] = i;
parent[v] = u;
u = v;
break;
}
}
if(i==-1) { /* 没有邻接点, 回溯到上一个点 */
if(--Count[dist[u]]==0) {
//顶点u在level dist[u]断层
break;
}
cur[u] = head[u]; /* 顶点u的所有边都试过了,没有出路, 更新了u的level后, 又从第一条边开始找 */
//找出level最小的邻接点
min_lev = n;
for(i=head[u];i!=-1;i=edge[i].next) {
if(edge[i].weight > 0) {
min_lev = min(dist[edge[i].v], min_lev);
}
}
dist[u] = min_lev + 1;
Count[dist[u]]++;
if(u != s ) u = parent[u]; /* 回退到上一个顶点 */
}
}
return max_flow;
}
int main(){
int i,j;
int a,b,c;
while(scanf("%d%d",&m,&n)!=EOF){
cnt = 0;
memset(head,-1,sizeof(head));
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,0);
}
printf("%d\n",isap(1,n));
}
return 0;
}