记录编号	271909	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-06-16 14:04:22	内存使用	0.31 MiB

#include <vector>
#include <iostream>
#include <fstream>
#include <list>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <cfloat>
#include <cmath>
using namespace std;
#define maxn 105
#define INF 0x7fffffff
class MCMF
{
	struct edge
	{
		int from, to;
		int rem, cost;
	};
	int s, t;
	int cost[maxn];
	int path[maxn];
	int flow[maxn];
	bool vis[maxn];
	vector<int> G[maxn];
	vector<edge> edges;
public:
	MCMF(int a, int b)
	{
		s = a;
		t = b;
	}
	void addedge(int f, int t, int fl, int ct)
	{
		edges.push_back((edge){f, t, fl, ct});
		edges.push_back((edge){t, f, 0, -ct});
		int k = edges.size();
		G[f].push_back(k-2);
		G[t].push_back(k-1);
	}
	bool spfa(int &fl, int &ct)
	{
		queue<int> q;
		memset(vis, false, sizeof(vis));
		for(int i = 0; i < maxn; i++)
			cost[i] = flow[i] = INF;
		vis[s] = true;
		flow[s] = INF;
		cost[s] = 0;
		q.push(s);
		while(q.size())
		{
			int c = q.front();
			q.pop();
			for(int i = 0; i < G[c].size(); i++)
			{
				edge &e = edges[G[c][i]];
				if(e.rem > 0 && cost[e.to] > cost[c] + e.cost)
				{
					cost[e.to] = cost[c] + e.cost;
					path[e.to] = G[c][i];
					flow[e.to] = min(flow[c], e.rem);
					if(!vis[e.to])
					{
						q.push(e.to);
						vis[e.to] = true;
					}
				}
			}
			vis[c] = false;
		}
		if(cost[t] == INF)
			return false;
		fl += flow[t];
		ct += cost[t] * flow[t];
		for(int cur = t; cur != s; cur = edges[path[cur]].from)
		{
			int p = path[cur];
			edges[p].rem -= flow[t];
			edges[p^1].rem += flow[t];
		}
		return true;
	}
	int mincmaxf(int &c)
	{
		int f = 0;
		c = 0;
		while(spfa(f, c));
		return f;
	}
};
FILE *fin = fopen("maxflowd.in", "r");
FILE *fout = fopen("maxflowd.out", "w");

int main()
{
	int n;
	int s, t;
	fscanf(fin, "%d %d %d", &n, &s, &t);
	MCMF mcmf(s, t);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int a, b;
			fscanf(fin, "%d %d", &a, &b);
			if(a == 0)continue;
			mcmf.addedge(i, j, a, b);
		}
	}
	int ans = 0;
	mcmf.mincmaxf(ans);
	fprintf(fout, "%d\n", ans);
	return 0;
}