iframe-proxy | Sunbelt Computer Software

136 lines (114 loc) · 1.91 KB

#include <cstdio>
#include <cstring>
#define VERTEX_COUNT 210
#define EDGE_COUNT 20000
using namespace std;
struct vertex
	int first_edge;
	int pree, prev;
}V[VERTEX_COUNT];
bool vis[VERTEX_COUNT];
struct edge
	int endp, next;
}E[EDGE_COUNT];
int ec = 2;
int ivc, iec;
int maxflow = 0;
int Q[VERTEX_COUNT];
int hp = 0, tp = 0;
inline int min(int x, int y)
	return x < y ? x : y;
void add_edge(int u, int v, int f)
	E[ec].next = V[u].first_edge;
	V[u].first_edge = ec;
	E[ec].endp = v;
	E[ec].flow = f;
inline void enqueue(int x)
	Q[tp++] = x;
inline int dequeue()
	return Q[hp++];
inline bool isempty()
	return hp == tp;
inline void empty()
	hp = tp = 0;
void Edmonds_Karp(int s, int t)
	bool has_ap;
		has_ap = false;
		memset(vis, false, sizeof(vis));
		enqueue(s);
		while (!isempty())
			int u = dequeue();
			for (int cur = V[u].first_edge; cur != 0; cur = E[cur].next)
				if (E[cur].flow > 0)
					if (E[cur].endp == t)
						has_ap = true;
						int p = u, pathmin = E[cur].flow;
						while (p != 1)
							pathmin = min(pathmin, E[V[p].pree].flow);
							p = V[p].prev;
						p = u;
						E[cur].flow -= pathmin;
						E[cur ^ 1].flow += pathmin;
						while (p != 1)
							E[V[p].pree].flow -= pathmin;
							E[V[p].pree ^ 1].flow += pathmin;
							p = V[p].prev;
						maxflow += pathmin;
						goto END;
					else if (vis[E[cur].endp] == false)
						V[E[cur].endp].pree = cur;
						V[E[cur].endp].prev = u;
						vis[E[cur].endp] = true;
						enqueue(E[cur].endp);
	} while (has_ap == true);
	// e.g. CodeVS - 1993.
	scanf("%d%d", &iec, &ivc);
	for (int i = 0; i < iec; i++)
		int u, v, f;
		scanf("%d%d%d", &u, &v, &f);
		add_edge(u, v, f);
		add_edge(v, u, 0);
	Edmonds_Karp(1, ivc);
	printf("%d", maxflow);

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

Edmonds-Karp.cpp

Latest commit

History

Edmonds-Karp.cpp

File metadata and controls