#include "NF_EK.h"
CNF_EK::CNF_EK(int vertex_count)
{
_N = vertex_count;
_Cap = new double*[_N];
for (int i = 0; i < _N; ++i)
{
_Cap[i] = new double[_N];
memset(_Cap[i], 0, _N * sizeof(double));
}
_Flow = new double*[_N];
for (int j = 0; j < _N; ++j)
{
_Flow[j] = new double[_N];
memset(_Flow[j], 0, _N * sizeof(double));
}
}
CNF_EK::~CNF_EK()
{
for (int i = 0; i < _N; ++i) delete[] _Cap[i];
delete[] _Cap;
for (int j = 0; j < _N; ++j) delete[] _Flow[j];
delete[] _Flow;
}
void CNF_EK::AddEdge(int from, int to, double cap)
{
_Cap[from][to] = cap;
}
double CNF_EK::MaxFlow(int s, int t)
{
double res = 0;// 最大流。
double* dis = new double[_N];// dis[i]表示从s到i的最小残量。
int* p = new int[_N];// 增广路中的上一节点。
queue<int> Q;
while (true)
{
memset(dis, 0, _N * sizeof(double));
dis[s] = DBL_MAX;
Q.push(s);
// 计算可增加流量。
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (int y = 0; y < _N; y++)
{
if (dis[y] == 0 && _Cap[x][y] > _Flow[x][y])
{
p[y] = x;
Q.push(y);
dis[y] = _Cap[x][y] - _Flow[x][y];
if (dis[y] > dis[x]) dis[y] = dis[x];
}
}
}
// 当网络中没有增广路径。
if (dis[t] == 0) break;
// 更新流量，沿着增广路增广。
for (int x = t; x != s; x = p[x])
{
_Flow[p[x]][x] += dis[t];
_Flow[x][p[x]] -= dis[t];
}
res += dis[t];
}
delete[] dis;
delete[] p;
return res;
}
void CNF_EK::Test()
{
CNF_EK di1(9);
di1.AddEdge(1, 2, 6);
di1.AddEdge(1, 3, 6);
di1.AddEdge(2, 4, 7);
di1.AddEdge(3, 5, 4);
di1.AddEdge(4, 5, 2);
di1.AddEdge(4, 6, 3);
di1.AddEdge(5, 7, 5);
di1.AddEdge(7, 6, 2);
di1.AddEdge(6, 8, 5);
di1.AddEdge(7, 8, 4);
printf("CNF_EK:%f\n", di1.MaxFlow(1, 8));
CNF_EK di2(6);
di2.AddEdge(1, 2, 4.1);
di2.AddEdge(1, 3, 6.1);
di2.AddEdge(2, 3, 2.1);
di2.AddEdge(2, 4, 3.1);
di2.AddEdge(3, 5, 4.1);
di2.AddEdge(4, 5, 5.1);
printf("CNF_EK:%f\n", di2.MaxFlow(1, 5));
CNF_EK di3(4);
double flow = 99999;
di3.AddEdge(0, 1, flow);
di3.AddEdge(0, 2, flow);
di3.AddEdge(1, 3, flow);
di3.AddEdge(2, 3, flow);
di3.AddEdge(1, 2, 1);
printf("CNF_EK:%f\n", di3.MaxFlow(0, 3));
printf("\n");
}
