HDU 2686 Matrix

题目链接

3376 Matrix Again

题目链接

题意：这两题是一样的，仅仅是数据范围不一样，都是一个矩阵，从左上角走到右下角在从右下角走到左上角能得到最大价值

思路：拆点。建图，然后跑费用流就可以，只是HDU3376这题，极限情况是300W条边，然后卡时间过了2333

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

const int MAXNODE = 600 * 600 * 2 + 5;

const int MAXEDGE = 4 * MAXNODE;

typedef int Type;

const Type INF = 0x3f3f3f3f;

struct Edge {

	int u, v;

	Type cap, flow, cost;

	Edge() {}

	Edge(int u, int v, Type cap, Type flow, Type cost) {

		this->u = u;

		this->v = v;

		this->cap = cap;

		this->flow = flow;

		this->cost = cost;

	}

};

struct MCFC {

	int n, m, s, t;

	Edge edges[MAXEDGE];

	int first[MAXNODE];

	int next[MAXEDGE];

	int inq[MAXNODE];

	Type d[MAXNODE];

	int p[MAXNODE];

	Type a[MAXNODE];

	void init(int n) {

		this->n = n;

		memset(first, -1, sizeof(first));

		m = 0;

	}

	void add_Edge(int u, int v, Type cap, Type cost) {

		edges[m] = Edge(u, v, cap, 0, cost);

		next[m] = first[u];

		first[u] = m++;

		edges[m] = Edge(v, u, 0, 0, -cost);

		next[m] = first[v];

		first[v] = m++;

	}

	bool bellmanford(int s, int t, Type &flow, Type &cost) {

		for (int i = 0; i < n; i++) d[i] = INF;

		memset(inq, false, sizeof(inq));

		d[s] = 0; inq[s] = true; p[s] = s; a[s] = INF;

		queue<int> Q;

		Q.push(s);

		while (!Q.empty()) {

			int u = Q.front(); Q.pop();

			inq[u] = false;

			for (int i = first[u]; i != -1; i = next[i]) {

				Edge& e = edges[i];

				if (e.cap > e.flow && d[e.v] > d[u] + e.cost) {

					d[e.v] = d[u] + e.cost;

					p[e.v] = i;

					a[e.v] = min(a[u], e.cap - e.flow);

					if (!inq[e.v]) {Q.push(e.v); inq[e.v] = true;}

				}

			}

		}

		if (d[t] == INF) return false;

		flow += a[t];

		cost += d[t] * a[t];

		int u = t;

		while (u != s) {

			edges[p[u]].flow += a[t];

			edges[p[u]^1].flow -= a[t];

			u = edges[p[u]].u;

		}

		return true;

	}

	Type Mincost(int s, int t) {

		Type flow = 0, cost = 0;

		while (bellmanford(s, t, flow, cost));

		return cost;

	}

} gao;

const int N = 600 * 600 + 5;

const int d[2][2] = {1, 0, 0, 1};

int n, num[N];

int get(int now, int k) {

	int x = now / n;

	int y = now % n;

	x += d[k][0];

	y += d[k][1];

	if (x < 0 || x >= n || y < 0 || y >= n) return -1;

	return x * n + y;

}

int main() {

	while (~scanf("%d", &n)) {

		gao.init(n * n * 2);

		for (int i = 0; i < n * n; i++) {

			scanf("%d", &num[i]);

			if (i == 0) gao.add_Edge(i, i + n * n, 2, -num[i]);

			else if (i == n * n - 1) gao.add_Edge(i, i + n * n, 2, -num[i]);

			else gao.add_Edge(i, i + n * n, 1, -num[i]);

		}

		for (int i = 0; i < n * n; i++) {

			for (int j = 0; j < 2; j++) {

				int next = get(i, j);

				if (next < 0 || next >= n * n) continue;

				gao.add_Edge(i + n * n, next, 2, 0);

			}

		}

		printf("%d\n", -gao.Mincost(0, n * n * 2 - 1) - num[0] - num[n * n - 1]);

	}

	return 0;

}