View Code of Problem 3074

#include <iostream>
#include <cstdio>
#include <cstring>
#include <memory.h>
#include <cmath>

using namespace std;

const int MAXV = 2e4 + 10;
const int MAXE = 2e5;
const int INF = 0x3f3f3f3f;

int tmp;
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, n);
	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(--gap[dep[u]] == 0)
				break;
			int minn = n;
			for(i = head[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)
{
	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 = 0;
	head[v] = cnt++;
}

int main(void)
{
	int fn, fm;
	while(scanf("%d%d", &fn, &fm) != EOF)
	{
		memset(head, -1, sizeof head);
		int a, b, c;
		cnt = src = 0, n = des = fn + 1;
		for(int i = 1; i <= fn; i++)
		{
			scanf("%d%d", &a, &b);
			addEdge(src, i, a);
			addEdge(i, src ,a);
			addEdge(des, i, b);
			addEdge(i, des, b);
		}
		for(int i = 0; i < fm; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			addEdge(a, b, c);
			addEdge(b, a, c);
		}
		printf("%d\n", iSap());
	}
	return 0;
}
/*
F:\temp\15299595.178182\Main.cc:5:20: error: memory.h: No such file or directory
*/

Double click to view unformatted code.


Back to problem 3074