USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归

郁闷。不小心覆盖了重写的。

 

英文原题 中文题译

 

最原始经典的网络流最大流问题，本身没什么好说的。网上关于网络流和算法的小blog不少，良莠不齐，这里推荐一篇辉夜的blog，里面有各个算法的大致介绍和简单评测。评测数据来自于topcoder上一篇更严谨的英文文章《Maximum Flow: Augmenting Path Algorithms Comparison》，值得一看。另外，维基百科上关于网络流的条目是不错的索引，可以从中找正规学术书籍例如目前最好的网络流专著Network Flows: Theory, Algorithms and Applications，以及一些算法图论方面的书籍。此外，作为算法手册的MIT的算法导论也是不错的，还有一本C++图论算法也可参考。所以这里也就不多说算法内容了。

 

在此题中实现了两个版本的SAP算法，一个是非递归的ISAP+GAP，相对于上面的blog中的代码去掉了BFS过程并增加可读性。一个是递归的多路增广：一般ISAP算法在得到一个增广轨后在全轨所有节点上均匀的去掉得到的流，而这个算法得到的不是一个增广轨，而是一个增广流：每个节点得到其所有后续节点可增广的流。这里有一个问题是反向狐是否会被多次使用？从算法结果上看是没有问题的，不过正确性需要另外证明。其非递归版是个严格的回溯算法，就没写了。等USACO Training 的全部做完，再回过头来整libary吧。

 

P.S. 网上一些所谓大牛的代码，实在没法读。叹一个。谁养成这种习惯写代码的话，到公司面试肯定被菜。当然，我贴在这里的代码为了减少行数也用了不少“,”，实际编程中并不推荐。

 

/*
ID: blackco3
TASK: ditch
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _max_node_(200), _max_val_(0x7fffffff);
 
struct t_edge{
    int to, cap; 
    t_edge *next, *rev; 
} *nodes[_max_node_], edge_buf[_max_node_<<1];
int n_node, n_edge, src, sink;
int dist[_max_node_], n_dis[_max_node_] ;

#ifndef __single_aug_path__
int aug_flow( int cur_node, int in_flow ) {
	if( cur_node == sink )
		return in_flow ;

	int remain=in_flow ;	
	for( t_edge *p_edge = nodes[cur_node]; p_edge; p_edge = p_edge->next) {
		if( !p_edge->cap || dist[cur_node] != dist[p_edge->to] + 1) 
			continue ;
		int cur_flow = aug_flow( p_edge->to , remain>p_edge->cap? p_edge->cap : remain );
		p_edge->cap -= cur_flow , p_edge->rev->cap += cur_flow, remain -= cur_flow; 
		if( dist[src]==n_node || !remain )
			return in_flow-remain ;
	}
	if( !(--n_dis[dist[cur_node]]) ) {
		dist[src]=n_node;    // GAP cut
		return in_flow-remain;
	}

	int min_dist = n_node;
    for(t_edge *p_edge = nodes[cur_node]; p_edge; p_edge = p_edge->next)
		min_dist = p_edge->cap ? min(min_dist, dist[p_edge->to]) : min_dist;
    dist[cur_node] = min_dist + 1, n_dis[ dist[cur_node] ]++;
	return in_flow-remain ;
}

int maxflow( ){
    int cur_node = src, tot_flow = 0;
    while( dist[src] < n_node )
		tot_flow += aug_flow( cur_node, _max_val_ ) ;
    return tot_flow;
}
#else
t_edge **cur_edge[_max_node_] ;
int prev[_max_node_];
int maxflow( ){
    int cur_node = src, tot_flow = 0;
    memcpy( cur_edge, nodes, sizeof(t_edge*)*n_node );
    while( dist[src] < n_node ){
        if(cur_node == sink){    // find an augmenting path
            int aug_flow = _max_val_;
            for(int i = src; i != sink; i = cur_edge[i]->to )
                aug_flow = min(aug_flow, cur_edge[i]->cap);
            for(int i = src; i != sink; i = cur_edge[i]->to ) 
                cur_edge[i]->cap -= aug_flow, cur_edge[i]->rev->cap += aug_flow;
            tot_flow += aug_flow, cur_node = src;
        }
 
        t_edge *p_edge;
        for( p_edge = cur_edge[cur_node]; p_edge; p_edge = p_edge->next)
			if( p_edge->cap > 0 && dist[cur_node] == dist[p_edge->to] + 1) {
				cur_edge[cur_node] = p_edge, prev[p_edge->to] = cur_node, cur_node = p_edge->to;
				break;
			}
		if( !p_edge ) {
			if( !(--n_dis[dist[cur_node]]))
				break;    // GAP cut
            cur_edge[cur_node] = nodes[cur_node];
            int min_dist = n_node;
            for(t_edge *p_edge = nodes[cur_node]; p_edge; p_edge = p_edge->next)
                min_dist = p_edge->cap>0 ? min(min_dist, dist[p_edge->to]) : min_dist;
            dist[cur_node] = min_dist + 1, n_dis[ dist[cur_node] ]++;
            cur_node = prev[cur_node]; 
        }
    }
    return tot_flow;
}
#endif
 
int main(){
	freopen("ditch.in", "r", stdin);
	freopen("ditch.out", "w", stdout);
	cin >> n_edge >> n_node ;
	t_edge *p_buf = edge_buf;
	for( int i=0; i<n_edge; i++ ){
		int from, to, cap ;
		cin >> from >> to >> cap ;
		from--, to-- ;
		p_buf->to=to, p_buf->cap=cap, p_buf->next=nodes[from], nodes[from]=p_buf, p_buf->rev=p_buf+1, p_buf++ ;
		p_buf->to=from, p_buf->cap=0, p_buf->next=nodes[to], nodes[to]=p_buf, p_buf->rev=p_buf-1, p_buf++ ;        
    }
	src=0, sink=n_node-1 ;
    cout << maxflow( ) << endl ;
    return 0;
}