View Code of Problem 3074

#pragma warning (disable:4996)
   
#include<stdio.h>
#include<string.h>




#define MAXN 20000
#define MAXE 300000
#define INF 1e9
int tmp, src, des, cnt;//src源点，des汇点，该代码标号均从0开始
int n, m;

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

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

int ISAP()
{
	int cur_fLow, max_fLow, u, insert, i;
	memset(dep, 0, sizeof(dep));//代表深度
	memset(gap, 0, sizeof(gap));
	memcpy(cur, head, n);
	max_fLow = 0;
	u = src;
	top = 0;
	while (dep[src] < n)
	{
		if (u == des)//当当前点运动到汇点
		{
			cur_fLow = INF;
			for (i = 0; i < top; ++i)//top栈顶，也就是将一条增广路径中所有的边全部压入一个栈中，然后从栈底开始，找出最小的流量，也就是该增广路径增加的流量
			{
				if (cur_fLow > edge[stack[i]].cap)
				{
					insert = i;
					cur_fLow = edge[stack[i]].cap;
				}
			}
			for (i = 0; i < top; ++i)//更新残量网络，同时增加反向弧
			{
				edge[stack[i]].cap -= cur_fLow;
				edge[stack[i] ^ 1].cap += cur_fLow;
			}
			max_fLow += cur_fLow;//最后总流量加上增加的流量
			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;//GAP优化
			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 max_fLow;
}

void addedge(int u, int v, int f)//正方向连一次边，反方向再连一次边，不过反向的流量为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 = 0;
	head[v] = cnt++;
}
//
//int main()
//{
//	while (scanf("%d%d", &m, &n) != EOF)
//	{
//		cnt = 0;
//		src = 0;
//		des = n - 1;
//		memset(head, -1, sizeof(head));
//		while (m--)
//		{
//			int a, b, c;
//			scanf("%d%d%d", &a, &b, &c);
//			--a, --b;
//			addedge(a, b, c);
//			//addedge(b, a, c);如果是无向边的加上这句  
//		}
//		int ans = ISAP();
//		printf("%d\n", ans);
//	}
//	return 0;
//}
int main(void)
{
	int fn, fm;
	scanf("%d%d", &fn, &fm);

	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);
		addedge(b, a, c);
	}
	printf("%d\n", ISAP());

	return 0;
}