View Code of Problem 3074

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 40010;
const int MAXM = 500000;

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

int head[MAXN];
int path[MAXN];
int dep[MAXN];
int src;
int des;
int cnt;
int n;
int m;

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

	edge[cnt].from = v;
	edge[cnt].to = u;
	edge[cnt].cap = f2;
	edge[cnt].next = head[v];
	head[v] = cnt++;
}

int dinic()
{
	int maxFlow = 0;
	int k, l, r, top, min;
	int u, v;
	for (;;)
	{
		memset(dep, -1, sizeof dep);
		for (l = dep[path[0] = src] = 0, r = 1; l != r;)
		{
			for (u = path[l++], v = head[u]; v != -1; v = edge[v].next)
			{
				if (edge[v].cap && dep[edge[v].to] == -1)
				{
					dep[edge[v].to] = dep[u] + 1;
					path[r++] = edge[v].to;
					if (edge[v].to == des)
					{
						l = r;
						break;
					}
				}
			}
		}
		if (dep[des] == -1)
			break;
		for (u = src, top = 0;;)
		{
			if (u == des)
			{
				for (k = 0, min = INF; k < top; k++)
				{
					if (min > edge[path[k]].cap)
						min = edge[path[l = k]].cap;
				}
				for (k = 0; k < top; k++)
				{
					edge[path[k]].cap -= min;
					edge[path[k] ^ 1].cap += min;
				}
				maxFlow += min;
				u = edge[path[top = l]].from;
			}
			for (v = head[u]; v != -1; v = edge[v].next)
			{
				if (edge[v].cap && dep[edge[v].to] == dep[u] + 1)
					break;
			}
			if (v != -1)
			{
				path[top++] = v;
				u = edge[v].to;
			}
			else
			{
				if (!top)
					break;
				dep[u] = -1;
				u = edge[path[--top]].from;
			}
		}
	}
	return maxFlow;
}

int main(void)
{
	//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", dinic());
	}
	return 0;
}