POJ 1273 Drainage Ditches 网络流模版

题目传送门

网络流模版题，本想水一水，莫想到因为没好好看题给跪了。

题目大意就是 给你一堆水洼地，还有一些水沟，最终让水洼里的水通过水沟流入溪流。

要留意的就是据说会有重边，需要额外处理。（第二次练习 DInic 时发现完全不需要）

再就是要看清题意 “  For any given ditch, water flows in only one direction ” 就是说是有向图，读题的时候专门留意了可是做题的时候却记了个无向图还专门加了个反向。结果坑了半个多小时。。WA了好几次。。深刻检讨！

写了两个代码，虽然都是零毫秒，不过要学习嘛。。

第一种是最简单的寻找增广路 Ford-Fulkerson 算法

#include <cstdio>
#include <cstring>
#include <vector>
#define INF 1<<30
#define N 222
using namespace std;
struct EDGE
{
int to, cap, rev;
};
vector<EDGE> g[N];
int ff[N][N];
bool used[N];
int n,m;
int dfs(int v,int t,int f){
if ( v == t ) return f;
used[v]= true;
for ( int i(0); i < g[v].size(); i++){
EDGE &e = g[v][i];
if ( !used[e.to] && e.cap > 0){
int d = dfs(e.to, t, min(f,e.cap));
if ( d > 0){
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow = 0;
while (1){
memset(used,0,sizeof(used));
int f = dfs(s,t,INF);
if (f) flow += f;
else return flow;
}
}
void add_edge(int from, int to, int cap){
g[from].push_back((EDGE){to,cap,g[to].size()});
g[to].push_back((EDGE){from,0,g[from].size()-1});
}
int main(){
freopen(“in.txt”,“r”,stdin);
while ( ~scanf("%d%d",&m,&n)){
for ( int i(0);i<N;i++) g[i].clear();
memset(ff,0,sizeof(ff));
while ( m– ){
int from,to,cap;
scanf("%d%d%d",&from,&to,&cap);
ff[from][to] += cap;
}
for ( int i(1);i<=n;i++){
for ( int j(1); j<=n;j++){
if ( ff[i][j] ){
add_edge(i,j,ff[i][j]);
}
}
}
printf("%d\n",max_flow(1,n));
}
return 0;
}

第二种是优化后的 Dinic 算法，方法是 对整个图加了一个分层，每次只找最短的增广路，找不到就一层一层下去。原书《挑战程序设计竞赛（巫泽俊 译）》里还有个 iter[] 表示当前弧，不过没看到用。所以我就擅自去掉了。

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define N 222
#define INF 1<<30
using namespace std;
struct EDGE{
int to, cap, rev;
};
vector<EDGE> g[N];
queue<int> que;
int dist[N];
int n, m;
void add_edge(int from, int to, int cap){
g[from].push_back((EDGE){to, cap, g[to].size()});
g[to].push_back((EDGE){from, 0, g[from].size() - 1});
}
void bfs(int s){
memset(dist, -1, sizeof(dist));
while ( !que.empty() ) que.pop();
dist[s] = 0;
que.push(s);
while (!que.empty()){
int v = que.front();
que.pop();
for ( int i(0); i != g[v].size(); i++){
EDGE &e = g[v][i];
if ( e.cap > 0 && dist[e.to] < 0){
dist[e.to] = dist[v] + 1;
que.push(e.to);
}
}
}
}
int dfs(int v, int t, int f){
if ( v == t ) return f;
for  ( int i(0); i != g[v].size(); i++){
EDGE &e = g[v][i];
if ( e.cap > 0 && dist[e.to] > dist[v]){
int d = dfs(e.to, t, min(f, e.cap));
if ( d > 0){
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int Dinic(int s, int t){
int flow = 0;
while (1){
bfs(s);
if (dist[t] < 0) return flow;
int f;
while ((f = dfs(s, t, INF)) > 0) flow += f;
}
}
int main(){
freopen(“in.txt”, “r”, stdin);
while ( ~scanf("%d%d", &m, &n)){
    for ( int i(0); i &lt; N; i++) g[i].clear();
    memset(ff,0,sizeof(ff));

    while (m--){
        int from, to, cap;
        scanf("%d%d%d", &amp;from, &amp;to, &amp;cap);
        add_edge(from,to,cap);
    }

    printf("%d\n", Dinic(1, n));
}
return 0;

}