POJ 3469最小割

我们从上面的图可以看到，如果这样建立图，那么我问题就转变为最小割的问题了。即求最大流。为什么这样是正确的呢

假设，没有额外费用的时候，我们从a流向b的流量，如a-1-b这时候流量只会取小的那个，相当于在a，b之间做出决定，要最小费用，究竟是那一边。

再不加入额外费用的时候，我们可以看到割最小是5，即1，2，3.然而加入了额外费用的时候，我们再割，1，2，3就发现了，这个图依然是联通的，从A-3-2-B

即我们加入了一条，割不动的边，来使的割集进行变化。即，割a还是b，不能像以前一样，选最小的那个了，还需要考虑，如果一个割a，一个割b，那么如果中间有边的话，那么就无法满足割。

即增加复杂度。最后跑一编流图就好了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
//#include<regex>
#include<cstdio>
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
const double esp = 1e-6;
const double pi = acos(-1.0);
const long long INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
typedef pair<int, int> pir;
int n, m;
int a[20005];
struct edge { int to, cap,rev; };
vector<edge>g[20010];
int level[20005];
int iter[20005];
void addedge(int s, int t,int cap)
{
	g[s].push_back(edge{ t,cap,(int)g[t].size() });//反边指向to的弧
	g[t].push_back(edge{ s,0,(int)g[s].size()-1 });
}//邻接表
void bfs(int s)
{
	memset(level, -1, sizeof(level));
	queue<int>que;
	que.push(s);
	level[s] = 0;
	while (!que.empty())
	{
		int temp = que.front();
		que.pop();
		up(i, 0, g[temp].size())
		{
			edge e = g[temp][i];
			if (level[e.to] < 0&&g[temp][i].cap>0)
			{
				level[e.to] = level[temp] + 1;
				que.push(e.to);
			}
		}
	}
}//bfs计算lelvel，相当于算每个点的势，方便dfs求最短路
int dfs(int s,int t,int f)
{
	int res = 0;
	if (s == t)return f;
	for (int &i = iter[s]; i < g[s].size(); i++ )//算过的弧不要再算了，因为
	//可能增广路不止一条，要重复进行dfs
	{
		edge &e = g[s][i];
		if (e.cap > 0 && level[s] < level[e.to])
		{
			int d = dfs(e.to, t, min(f, e.cap));//求最小的那个
			if (d > 0)
			{
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
	
}
int min_flow(int s,int t)
{
	int res = 0;
	int d = 0;
	while (1)
	{
		bfs(s);
		if (level[t] < 0)
		{
			return res;
		}//无法继续增广
		memset(iter, 0, sizeof(iter));
		while ((d = dfs(s, t, inf)) > 0)//当前增广路的增广
		{
			res += d;
		}
	}
}//dinic算法
int main()
{
	cin >> n >> m;
	int a = 0;
	upd(i, 1, n)
	{
		scanf("%d", &a);
		addedge(0, i, a);
		scanf("%d", &a);
		addedge(i, n + 1, a);
	}
	int b, w;
	upd(i, 1, m)
	{
		scanf("%d%d%d", &a, &b, &w);
		addedge(a, b, w);
		addedge(b, a, w);
	}//建图
	cout << min_flow(0,n+1) << endl;
	return 0;
}