View Code of Problem 3074

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXV = 20010;
const int MAXE = 400000;
const int INF = 0x3f3f3f3f;

int src;
int des;
int cnt;
int n;//sum of v
int m;//sum of e

struct Edge
{
	int from, to;
	int next, cap;
}edge[MAXE];

int head[MAXV];
int gap[MAXV], dep[MAXV], cur[MAXV], stack[MAXV], top;

int iSap()
{
	int curFlow, maxFlow, u, insert, i;
	memset(dep, 0, sizeof dep);
	memset(gap, 0, sizeof gap);
	memcpy(cur, head, sizeof(head));
	maxFlow = 0;
	u = src;
	top = 0;
	while (dep[src] < n)
	{
		if (u == des)
		{
			curFlow = INF;
			for (i = 0; i < top; i++)
			{
				if (curFlow > edge[stack[i]].cap)
				{
					insert = i;
					curFlow = edge[stack[i]].cap;
				}
			}
			for (i = 0; i < top; i++)
			{
				edge[stack[i]].cap -= curFlow;
				edge[stack[i] ^ 1].cap += curFlow;
			}
			maxFlow += curFlow;
			u = edge[stack[top = insert]].from;
		}
		for (i = cur[u]; i != -1; i = edge[i].next)
		{
			if ((edge[i].cap > 0) && (dep[u] == dep[edge[i].to] + 1))
				break;
		}
		if (i != -1)
		{
			stack[top++] = i;
			u = edge[i].to;
		}
		else
		{
			if (0 == --gap[dep[u]])
				break;
			int minn = n;
			for (i = cur[u]; i != -1; i = edge[i].next)
			{
				if (edge[i].cap > 0)
					minn = (minn > dep[edge[i].to]) ? (cur[u] = i, dep[edge[i].to]) : minn;
			}
			gap[dep[u] = minn + 1]++;
			if (u != src)
				u = edge[stack[--top]].from;
		}
	}
	return maxFlow;
}

void addEdge(int u, int v, int f, int c = 0)
{
	edge[cnt].next = head[u];
	edge[cnt].from = u;
	edge[cnt].to = v;
	edge[cnt].cap = f;
	head[u] = cnt++;
	edge[cnt].next = head[v];
	edge[cnt].from = v;
	edge[cnt].to = u;
	edge[cnt].cap = c;
	head[v] = cnt++;
}

int main(void)
{
	//FILE *fp;
	//freopen("C:\\Users\\Administrator\\Desktop\\test.txt", "r", stdin);
	int fn, fm;
	while (scanf("%d%d", &fn, &fm) != EOF)
	{
		memset(head, -1, sizeof head);
		int a, b, c;
		cnt = src = 0, des = fn + 1;
		n = des + 1;
		for (int i = 1; i <= fn; i++)
		{
			scanf("%d%d", &a, &b);
			addEdge(src, i, a);
			addEdge(i, des, b);
		}
		for (int i = 0; i < fm; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			addEdge(a, b, c, c);
		}
		printf("%d\n", iSap());
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3074