Rockdu's Blog

题目描述

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入输出格式

输入格式：

第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式：

一个数,为最大和

输入输出样例

3 1
1 2 3
0 2 1
1 4 2

11

说明

每个格子中的数不超过1000

考虑把每一个格子拆成两个点，一个连接所有的入度，一个连接所有的出度，两点之间连一条费用为格子中的数流量为1的边表示可以取数1次，再连一条流量为INF费用为0的边表示取完还能走。对应能到达的格子连边流量为INF，费用为0。这样我们只要把起点拆出来的两个点之间连的流量为INF费用为0的边换成流量为k就好了。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxm = 100005, maxn = 105, maxp = maxn * maxn;
const int IN = 0, OUT = 1, inf = 0x3f3f3f3f;
int n, k;
struct edge {
	int v, cost, w, next;
}e[maxm << 1];
int head[maxp], cnt, pos[maxn][maxn][2], mp[maxn][maxn], pcnt;
int st, ed;

void adde(const int &u, const int &v, const int &w, const int &cost) {
	e[++cnt] = (edge) {v, cost, w, head[u]};
	head[u] = cnt;
	e[++cnt] = (edge) {u, -cost, 0, head[v]};
	head[v] = cnt;
}

int dis[maxp], vis[maxp], fa[maxp], eid[maxp], ans;
void SPFA(int s, int t) {
	queue<int > q;
	for(register int i = 0; i <= pcnt; ++i) dis[i] = -inf;
	memset(vis, 0, sizeof(vis));
	memset(fa, 0, sizeof(fa));
	q.push(s), dis[s] = 0, vis[s] = 1;
	while(!q.empty()) {
		int u = q.front();
		q.pop(), vis[u] = 0;
		for(register int i = head[u]; i; i = e[i].next) {
			if(!e[i].w) continue;
			int v = e[i].v;
			if(dis[v] < dis[u] + e[i].cost) {
				dis[v] = dis[u] + e[i].cost;
				fa[v] = u, eid[v] = i;
				if(vis[v]) continue;
				q.push(v), vis[v] = 1;
			}
		}
	}
}

void ExtFlow(int s, int v, int & mn) {
	if(v == s) return;
	mn = min(e[eid[v]].w, mn);
	ExtFlow(s, fa[v], mn);
	e[eid[v]].w -= mn;
	e[eid[v] ^ 1].w += mn;
	ans += e[eid[v]].cost * mn;
}

int GetAns(int s, int t) {
	int mn = inf;
	while(1) {
		SPFA(s, t);
		if(dis[t] == -inf) break;
		mn = inf, ExtFlow(s, t, mn);
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &k);
	cnt = 1;
	for(register int i = 1; i <= n; ++i)
		for(register int j = 1; j <= n; ++j) {
			scanf("%d", &mp[i][j]);
			pos[i][j][IN] = ++pcnt; 
			pos[i][j][OUT] = ++pcnt;
			if(i == 1 && j == 1) continue;
			adde(pos[i][j][IN], pos[i][j][OUT], inf, 0);
			adde(pos[i][j][IN], pos[i][j][OUT], 1, mp[i][j]);
		}
	for(register int i = 1; i < n; ++i) adde(pos[n][i][OUT], pos[n][i + 1][IN], inf, 0);
	for(register int i = 1; i < n; ++i) adde(pos[i][n][OUT], pos[i + 1][n][IN], inf, 0);
	for(register int i = 1; i < n; ++i)
		for(register int j = 1; j < n; ++j) {
			adde(pos[i][j][OUT], pos[i + 1][j][IN], inf, 0);
			adde(pos[i][j][OUT], pos[i][j + 1][IN], inf, 0);
		}
	adde(pos[1][1][IN], pos[1][1][OUT], k - 1, 0);
	adde(pos[1][1][IN], pos[1][1][OUT], 1, mp[1][1]);
	st = pos[1][1][IN], ed = pos[n][n][OUT];
	printf("%d", GetAns(st, ed));
	return 0;
}