---
# System prepended metadata

title: 危橋

---

# 危橋

```cpp=
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <utility>
#include <vector>

#define MOD (1000000007)
#define INF (0x3f3f3f3f)
#define PREC (0.0000001)
#define X first
#define Y second

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

class maxFlow{

	int** cap;
	int *vstd;
	int *par;
	vector<int> *mp;
	int vs;
	queue<int> que;
	bool flag;
	int s, e;
	int ecnt = 0;

	public:
	int ans;
	maxFlow(){};
	maxFlow(int n, int start, int end) //Numbers of node, start, end
	{
		vs = n;
		s = start;
		e = end;
		flag = true;
		vstd = new int[n + 10];
		par = new int[n + 10];
		mp = new vector<int>[n + 10];
		cap = new int*[n + 10];
		memset(vstd, 0, sizeof(int) * (n + 10));
		for(int i = 0; i < n + 10; i++)
		{
			cap[i] = new int[n + 10];
			memset(cap[i], 0, sizeof(int) * (n + 10));
		}
	}

	void addEdge(int from, int to, int cp)
	{
		mp[from].push_back(to);
		mp[to].push_back(from);

		cap[from][to] += cp;
	}

	int exe()
	{
		int count = 1;
		int temp;
		int mn;
		flag = true;
		ans = 0;
		while(flag)
		{
			flag = false;
			ecnt++;

			que.push(s);
			vstd[s] = count;
			par[s] = -1;

			while(!que.empty())
			{
				temp = que.front();
				que.pop();

				if(flag) continue;

				if(temp == e)
				{
					flag = true;
					mn = INF;

					while(par[temp] != -1)
					{
						if(cap[par[temp]][temp] < mn) mn = cap[par[temp]][temp];
						temp = par[temp];
					}

					ans += mn;
					temp = e;
					while(par[temp] != -1)
					{
						cap[par[temp]][temp] -= mn;
						cap[temp][par[temp]] += mn;

						temp = par[temp];
					}

					continue;
				}

				for(int v : mp[temp])
				{
					if(vstd[v] != count && cap[temp][v] > 0)
					{
						vstd[v] = count;
						que.push(v);
						par[v] = temp;
					}
				}
			}

			count++;
		}

		fprintf(stderr, "choose : %d\n", ecnt);

		return ans;
	}
	
};


void init()
{
	
}
 
void solve()
{
	int v, e;
	scanf("%d %d", &v, &e);

	maxFlow mxf(v, 1, v);

	int from, to, w;
	for(int i = 0; i < e; i++)
	{
		scanf("%d %d %d", &from, &to, &w);

		if(w < 0)
		{
			mxf.addEdge(from, to, -w);
		}
	}

	printf("%d\n", mxf.exe());
}
 
int main()
{
	// int n;
	// scanf("%d", &n);
	
	// while(n--)
	{
		init();
		solve();
		
	}
	return 0;
}

```