记录编号	245616	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-04-03 21:42:12	内存使用	0.31 MiB

#include <vector>
#include <queue>
#include <cstdio>
#include <fstream>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <list>
#include <functional>
using namespace std;

#ifdef __linux__
	#define IP "maxflowa.in"
	#define OP "maxflowa.out"
#else
	#define IP "CONIN$"
	#define OP "CONOUT$"
#endif

struct edge
{
	int from, to, rem;
};

class dinic
{
	int s,t;
	vector<edge> edges;
	vector<int> G[101];
	bool vis[101];
	int dist[101];
public:
	dinic(int ss, int tt)
	{
		s = ss;
		t = tt;
	}
	
	void add(int f, int t, int c)
	{
		edges.push_back((edge){f, t, c});
		edges.push_back((edge){t, f, 0});
		int m = edges.size();
		G[f].push_back(m-2);
		G[t].push_back(m-1);
	}
	
	bool bfs()
	{
		memset(vis, false, sizeof(vis));
		queue<int> q;
		q.push(s);
		vis[s] = true;
		dist[s] = 0;
		
		while(q.size())
		{
			int u = q.front();
			q.pop();
			for(int i = 0; i < G[u].size(); i++)
			{
				edge& e = edges[G[u][i]];
				if(!vis[e.to] && e.rem > 0)
				{
					vis[e.to] = true;
					dist[e.to] = dist[u] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	
	int dfs(int cur, int flow)
	{
		if(cur == t || flow == 0)return flow;
		int n;
		int r = 0;
		for(int i = 0; i < G[cur].size(); i++)
		{
			edge& e = edges[G[cur][i]];
			if(dist[e.to] == dist[cur] + 1 && (n = dfs(e.to, min(flow, e.rem))) > 0)
			{
				r += n;
				e.rem -= n;
				flow -= n;
				edges[G[cur][i]^1].rem += n;
				if(flow == 0)break;
			}
		}
		return r;
	}
	
	int maxflow(int sf)
	{
		int res = 0;
		while(bfs())
			res += dfs(s, sf);
		return res;
	}
};

ifstream IF(IP);
ofstream OF(OP);

int main()
{
	ios::sync_with_stdio(false);
	int n;
	IF >> n;
	dinic sss(1, n);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int k;
			IF >> k;
			if(k)sss.add(i, j, k);
		}
	}
	OF << sss.maxflow(0x7fffffff);
	return 0;
}