/**
* //////////////////
* // MAXIMUM FLOW //
* //////////////////
*
* This file is part of my library of algorithms found here:
* http://www.palmcommander.com:8081/tools/
* LICENSE:
* http://www.palmcommander.com:8081/tools/LICENSE.html
* Copyright (c) 2004
* Contact author:
* igor at cs.ubc.ca
**/
/****************
* Maximum flow * (Ford-Fulkerson on an adjacency matrix)
****************
* Takes a weighted directed graph of edge capacities as an adjacency
* matrix 'cap' and returns the maximum flow from s to t.
*
* PARAMETERS:
* - cap (global): adjacency matrix where cap[u][v] is the capacity
* of the edge u->v. cap[u][v] is 0 for non-existent edges.
* - n: the number of vertices ([0, n-1] are considered as vertices).
* - s: source vertex.
* - t: sink.
* RETURNS:
* - the flow
* - fnet contains the flow network. Careful: both fnet[u][v] and
* fnet[v][u] could be positive. Take the difference.
* - prev contains the minimum cut. If prev[v] == -1, then v is not
* reachable from s; otherwise, it is reachable.
* DETAILS:
* FIELD TESTING:
* - Valladolid 10330: Power Transmission
* - Valladolid 653: Crimewave
* - Valladolid 753: A Plug for UNIX
* - Valladolid 10511: Councilling
* - Valladolid 820: Internet Bandwidth
* - Valladolid 10779: Collector's Problem
* #include <string.h>
* #include <queue>
**/
#include <string.h>
// the maximum number of vertices
#define NN 1024
// adjacency matrix (fill this up)
int cap[NN][NN];
// flow network
int fnet[NN][NN];
// BFS
int q[NN], qf, qb, prev[NN];
int fordFulkerson( int n, int s, int t )
{
// init the flow network
memset( fnet, 0, sizeof( fnet ) );
int flow = 0;
while( true )
{
// find an augmenting path
memset( prev, -1, sizeof( prev ) );
qf = qb = 0;
prev[q[qb++] = s] = -2;
while( qb > qf && prev[t] == -1 )
for( int u = q[qf++], v = 0; v < n; v++ )
if( prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] )
prev[q[qb++] = v] = u;
// see if we're done
if( prev[t] == -1 ) break;
// get the bottleneck capacity
int bot = 0x7FFFFFFF;
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
bot <?= cap[u][v] - fnet[u][v] + fnet[v][u];
// update the flow network
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
fnet[u][v] += bot;
flow += bot;
}
return flow;
}
//----------------- EXAMPLE USAGE -----------------
int main()
{
memset( cap, 0, sizeof( cap ) );
int numVertices = 100;
// ... fill up cap with existing edges.
// if the edge u->v has capacity 6, set cap[u][v] = 6.
cout << fordFulkerson( numVertices, s, t ) << endl;
return 0;
}
用C++写的复杂网络图论算法
5星 · 超过95%的资源 需积分: 50 102 浏览量
2012-10-26
21:04:20
上传
评论 2
收藏 9KB RAR 举报
gracezhao805
- 粉丝: 0
- 资源: 2
最新资源
- 同态加密python.zip
- 基于Python的PCA人脸识别算法的原理及实现代码详解+源码+详细代码解析+开发文档+数据(毕业设计&课程设计&项目开发)
- Decision tree20240105(1).ipynb
- zuoyezuoyezuoye
- zuoyezuoyezuoye
- 机械设计电机转子装配设备sw22非常好的设计图纸100%好用.zip
- 作业作业作业作业作业作业
- xdotool.c
- RLMD鲁棒性局部均值分解信号分量可视化(Matlab完整源码和数据)
- Screenshot_2024-04-26-17-17-26-36_9d26c6446fd7bb8e41d99b6262b17def.jpg
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
- 1
- 2
前往页