网络流——最大流算法 SAP
第 1 页 共 1 页
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define maxn 20010
#define maxe 200000
#define maxint 2147483647
#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)
using namespace std;
typedef struct edge
{
int v, c, next, op;
}edge;
edge g[maxe];
int first[maxn], h[maxn], cnt[maxn];
int n, total_edge, S, T;
// d = 0 有向边 ，d = 1 无向边
void add(int u, int v, int c, int d)
{
++total_edge;
g[total_edge].v = v;
g[total_edge].c = c;
g[total_edge].op = total_edge + 1;
g[total_edge].next = first[u];
first[u] = total_edge;
++total_edge;
g[total_edge].v = u;
g[total_edge].c = c * d;
g[total_edge].op = total_edge - 1;
g[total_edge].next = first[v];
first[v] = total_edge;
}
void ini(void)
{
int m;
scanf("%d%d", &m, &n );
while ( m-- )
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
add(u, v, c, 0);
}
}
int DFS(int u, int flow)
{
if (u == T)
return (flow);
int minh = n - 1;
int ct = 0;
int temp = first[u];
while ((temp != -1) && ( flow ))
{
int c = g[temp].c;
int v = g[temp].v;
if (c)
{
if (h[u] == h[v] + 1)
{
int k = DFS(v, min(c, flow));
if (k)
{
g[temp].c -= k;
g[g[temp].op].c += k;
flow -= k;
ct += k;
}
if (h[S] >= n)
return (ct);
}
minh = min(minh, h[v]);
}
temp = g[temp].next;
}
if (ct) return (ct);
--cnt[h[u]];
if (cnt[h[u]] == 0) h[S] = n;
h[u] = minh + 1;
++cnt[h[u]];
return (0);
}
void work(int _S,int _T)
{
S = _S;
T = _T;
memset( h, 0, sizeof (h));
memset( cnt, 0, sizeof(cnt));
int flow = 0;
while ( h[S] < n )
{
flow += DFS( S, maxint );
}
printf("%d",flow);
}
int main()
{
total_edge = 0;
memset( first, -1, sizeof(first));
ini();
work(1, n);
return(0);
}
