本文主要是介绍最大流、 最小费用最大流终极版模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大流
const int inf = 1000000000 ;
const int maxn = 20000 , maxm = 500000 ;
struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}
};
int sourse , meet ;
int id ;
Edge e[maxm*2 + 10] ;
int g[maxn + 10] ;void add(int u , int v , int f){e[++id] = Edge(v , f ,g[u]) ;g[u] = id ;e[++id] = Edge(u , 0 , g[v]) ;g[v] = id ;
}queue <int> que ;
bool vis[maxn + 10] ;
int dist[maxn + 10] ;void bfs(){memset(dist , 0 , sizeof(dist)) ;while(! que.empty()) que.pop() ;que.push(sourse) ;vis[sourse] = 1 ;while(! que.empty()){int u = que.front() ; que.pop() ;for(int i = g[u] ; i ; i = e[i].next){int v = e[i].v ;if(e[i].f && !vis[v]){que.push(v) ;dist[v] = dist[u] + 1 ;vis[v] = 1 ;}}}
}int dfs(int u , int delta){if(u == meet) return delta ;int ans = 0 ;for(int i = g[u] ; i && delta ; i = e[i].next){int v = e[i].v ;if(e[i].f && dist[v] == dist[u] + 1){int d = dfs(v , min(delta , e[i].f)) ;e[i].f -= d ;e[i^1].f += d ;delta -= d ;ans += d ;}}return ans ;
}int maxflow(){int ans = 0 ;while(1){memset(vis , 0 , sizeof(vis)) ;bfs() ;if(! vis[meet]) return ans ;ans += dfs(sourse , inf) ;}
}void init(){memset(g , 0 , sizeof(g)) ;id = 1 ;
}最小费用最大流
const int maxn = 5000 ;
const int maxm = 50000 ;
const int inf = 1000000000 ;
struct Edge{int v , f , w , next ;Edge(){}Edge(int _v , int _f , int _w , int _next):v(_v),f(_f),w(_w),next(_next){}
};
int g[maxn + 10] ;
Edge e[maxm + 10] ;
int source , meet ;
int id ;void add(int u , int v , int f , int w){e[++id] = Edge(v , f , w , g[u]) ;g[u] = id ;e[++id] = Edge(u , 0 , -w , g[v]) ;g[v] = id ;
}queue<int> que ;
bool in[maxn + 10] ;
int dist[maxn + 10] ;
int pv[maxn + 10] , pe[maxn + 10] ;int bfs(){while(! que.empty()) que.pop() ;que.push(source) ;memset(dist , 63 , sizeof(dist)) ;dist[source] = 0 ;in[source] = 1 ;while(! que.empty()){int u = que.front() ; que.pop() ;in[u] = 0 ;for(int i = g[u] ; i ; i = e[i].next){int v = e[i].v ;if(e[i].f > 0 && dist[u] + e[i].w < dist[v]){dist[v] = dist[u] + e[i].w ;pv[v] = u ;pe[v] = i ;if(! in[v]){in[v] = 1 ; que.push(v) ;}}}}return dist[meet] < inf ;
}int augment(){int u = meet ;int delta = inf ;while(u != source){delta = min(delta , e[pe[u]].f) ;u = pv[u] ;}u = meet ;while(u != source){e[pe[u]].f -= delta ;e[pe[u] ^ 1].f += delta ;u = pv[u] ;}return dist[meet] * delta ;
}int mincostflow(){int ans = 0 ;while(bfs()) ans += augment() ;return ans ;
}void init(){memset(g , 0 , sizeof(g)) ;id = 1 ;
}这篇关于最大流、 最小费用最大流终极版模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
