我用的模板和poj1273一样


#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 10010, maxm = 100010;
const int infinit = 0x3fffffff;

class Dinic
{
private:
	struct edge
	{
		int u, v, flow;
		edge *next, *rev;
	};
	edge *edges[maxn], epool[maxm];
	int n, ecnt, s, t; // Nodes, EDGE_POOL_COUNTER, source, sink
	int level[maxm];
	bool __addedge(int u, int v, int flow1, int flow2)
	{
		edge *p = &epool[ecnt++], *q = &epool[ecnt++];
		p -> u = u; p -> v = v; p -> flow = flow1;
			p -> next = edges[u]; edges[u] = p; p -> rev = q;
		q -> u = v; q -> v = u; q -> flow = flow2;
			q -> next = edges[v]; edges[v] = q; q -> rev = p;
		return true;
	}
	queue<int> que;
	bool __makelevel(void)
	{
		memset(level, 0, sizeof(level));
		while (!que.empty()) que.pop();
		level[s] = 1; que.push(s);
		while (!que.empty())
		{
			int p = que.front();
			que.pop();
			for (edge* ep = edges[p]; ep; ep = ep -> next)
				if (ep -> flow > 0 && !level[ep -> v])
					level[ep -> v] = level[p] + 1,
					que.push(ep -> v);
			if (level[t] > 1)
				return true;
		}
		return false;
	}
	int __find(int p, int mn)
	{
		if (p == t)
			return mn; // This is the last node
		int tmp = 0, alf = 0;
		for (edge* ep = edges[p]; ep && alf < mn; ep = ep -> next)
		{
			if (ep -> flow && level[ep -> v] == level[p] + 1)
			{
				tmp = __find(ep -> v, min(mn, ep -> flow));
				if (tmp)
				{
					alf += tmp;
					ep -> flow -= tmp;
					ep -> rev -> flow += tmp;
					return tmp;
				}
			}
		}
		if (!alf)
			level[p] = 0;
		return 0; // Which means failure
	}
public:
	bool addedge(int u, int v, int flow) {
		return __addedge(u, v, flow, 0); }
	bool addedge(int u, int v, int flow1, int flow2) {
		return __addedge(u, v, flow1, flow2); }
	bool init(void)
	{
		memset(edges, 0, sizeof(edges));
		memset(epool, 0, sizeof(epool));
		memset(level, 0, sizeof(level));
		n = s = t = ecnt = 0;
		return true;
	}
	Dinic(void) {
		init(); }
	bool set_params(int _n, int _s, int _t)
	{
		if (_s <= 0 || _n < 2 || _t > _n)
			return false;
		n = _n; s = _s; t = _t;
		return true;
	}
	int result;
	bool run_maxflow(void)
	{
		int sum = 0, tmp, found = 1;
		while (__makelevel())
		{
			found = 0;
			while (tmp = __find(s, infinit))
				sum += tmp,
				found = 1;
			if (!found)
				break;
		}
		result = sum;
		return true;
	}
	int get_maxflow(void)
	{
		return result;
	}
};

• Re:求问样例为什么用Dinic跑得6而不是13 (55) expert971 2016-04-06 15:41:29
• Re:求问样例为什么用Dinic跑得6而不是13 (32) 47301 2016-05-12 21:18:31