记录编号	143126	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 数字梯形	最终得分	100
用户昵称	Sasuke	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-12-13 08:44:19	内存使用	3.49 MiB

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int Sz = 1e5, Inf = 0x7f7f7f7f;

struct Edge {
	int v, Next, f, c, d;
	Edge() {}
	Edge(int v, int n, int f, int c, int d): v(v), Next(n), f(f), c(c), d(d) {}
} e[Sz];
int head[Sz], cnt = 1;

void AddEdge(int u, int v, int c, int k) {
	e[++cnt] = Edge(v, head[u], 0, c,  k); head[u] = cnt;
	e[++cnt] = Edge(u, head[v], 0, 0, -k); head[v] = cnt;
}

int s, t, flow, cost, dis[Sz], aug[Sz], p[Sz];
queue <int> q;
bool inq[Sz];

bool SPFA() {
	memset(dis, 0x7f, sizeof dis);
	q.push(s); inq[s] = 1; dis[s] = 0; aug[s] = Inf;
	while (!q.empty()) {
		int u = q.front(); 
		for(int E = head[u], v; E; E = e[E].Next) 
			if (dis[v = e[E].v] > dis[u]+e[E].d && e[E].c > e[E].f) {
				dis[v] = dis[u]+e[E].d; 
				p[v] = E;
				aug[v] = min(aug[u], e[E].c-e[E].f);
				if (!inq[v])
					q.push(v), inq[v] = 1;
			}
		q.pop(); inq[u] = 0;
	}
	if (dis[t] == Inf) return 0;
	int f = aug[t];
	flow += f; cost += f*dis[t];
	for(int i = t; i - s; i = e[p[i]^1].v)
		e[p[i]].f += f, e[p[i]^1].f -= f;
	return 1;
}

int MinCost() {
	flow = cost = 0;
	for(int i = 2; i <= cnt; ++i) e[i].f = 0;
	while (SPFA());
	return cost;
}

const int Sz2 = 99;
int m, n, loc[Sz2][Sz2], tot;

int main() {
	freopen("digit.in", "r", stdin);
	freopen("digit.out", "w", stdout);
	
	scanf("%d %d", &m, &n);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < i+m; ++j)
			loc[i][j] = (tot += 2);
	s = tot+2; t = tot+4;
	for(int i = 0, d; i < n; ++i)
		for(int j = 0; j < i+m; ++j) 
			AddEdge(loc[i][j]^1, loc[i+1][j], 1, 0),
			AddEdge(loc[i][j]^1, loc[i+1][j+1], 1, 0),
			scanf("%d", &d), AddEdge(loc[i][j], loc[i][j]^1, 1, -d);
	for(int i = 0; i < m; ++i) AddEdge(s, loc[0][i], 1, 0);
	for(int i = 0; i < n-1+m; ++i) AddEdge(loc[n-1][i]^1, t, 1, 0);
	printf("%d\n", -MinCost());
	
	for(int i = 2; i <= cnt; i += 2) 
		if ((e[i].v ^ e[i^1].v) == 1) e[i].c = Inf;
		else if (e[i].v == t) e[i].c = Inf;
	printf("%d\n", -MinCost());
	
	for(int i = 2; i <= cnt; i += 2)
		if (e[i^1].v - s) e[i].c = Inf;
	printf("%d\n", -MinCost());
}