2 | 4月 | 2016 | 超客的水墨烟雨

poj3422

maksyuki 发表于 oj 分类，标签: 图论(网络流)-费用流

02 4月 2016

Kaka's Matrix Travels

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the Ktravels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

3 2
1 2 3
0 2 1
1 4 2

Sample Output

Source

POJ Monthly--2007.10.06, Huang, Jinsong

题目类型：最小费用最大流

算法分析：建图时需要拆点，将每个点A拆成点A’和点A”，从A’向A”先连一条容量为1，花费为该点值的有向边，再连一条容量为k-1，花费为0的有向边(第一条边表示第一次到达该位置时可以拿走cost价值的东西，第二条边表示该点在拿完之后没有了，但是可以走k-1步)。若A点存在右边相邻或者是下面相邻的点B，则从A”向B’连一条容量为k，花费为0的有向边。最后再分别建一个源点和汇点，源点和1”相连容量为k，花费为0，2*n*n + 1和汇点相连容量为k，花费为0。最后跑一个最小费用流即可。注意这里边表的个数！！！

/*************************************************
Author        :supermaker
Created Time  :2016/4/1 20:26:51
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 6000 + 66;

struct Node
{
	int to, nxt, c, f, cost;	
};

Node edge[maxn*6];
int head[maxn], edgelen;

void Init ()
{
	memset (head, -1, sizeof (head));
	memset (edge, -1, sizeof (edge));
	edgelen = 0;
}

void AddEdge (int cost, int u, int v, int w, int rw = 0)
{
	edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;
	edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;
	edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;
	edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;
}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];
int N;

bool spfa (int s, int e)
{
	for	(int i = 0; i <= N; i++)
	{
		dis[i] = INF;
		inq[i] = cnt[i] = 0;
		par[i] = -1;
	}
	dis[s] = 0;
	queue <int> qu;
	qu.push (s);
	inq[s]++, cnt[s]++;
	while (!qu.empty ())
	{
		int u = qu.front (); qu.pop (); inq[u]--;
		if (cnt[u] > N) 
		{
			DB ("hi");
			return false;	
		}

		for (int i = head[u]; i != -1; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)
			{
				dis[v] = dis[u] + edge[i].cost;
				par[v] = i; 
				if (!inq[v])
				{
					qu.push (v);
					inq[v]++, cnt[v]++;
				}
			}
		}
	}
	if (par[e] == -1) return false;
	return true;
}

int allcost;
int MinCostMaxFlow (int s, int e)
{
	int res = 0;
	allcost = 0;
	while (spfa (s, e))
	{
		int minval = INF;
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
			minval = min (minval, edge[i].c - edge[i].f);
		for (int i = par[e]; i != -1; i = par[edge[i^1].to])
		{
			edge[i].f += minval;
			edge[i^1].f -= minval;
			allcost += edge[i].cost * minval;
		}
		res += minval;
		//DB (res);
	}
	return res;
}

int g[66][66];

int main()
{
    //CFF;
    //CPPFF;
   	int n, k;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf ("%d", &g[i][j]);
		Init ();
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				int u = (i - 1) * n + j;
				AddEdge (-g[i][j], u, u + n * n, 1);
				AddEdge (0, u, u + n * n, k - 1);
				if (i + 1 <= n)
					AddEdge (0, u + n * n, u + n, k);
				if (j + 1 <= n)
					AddEdge (0, u + n * n, u + 1, k);
				//DB (u), DB (u + n * n);
			}
		
		AddEdge (0, 0, 1, k);
		AddEdge (0, 2 * n * n, 2 * n * n + 1, k);
		N = 2 * n * n + 2;
		MinCostMaxFlow (0, 2 * n * n + 1);
		printf ("%d\n", -allcost);
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

/*************************************************

Author :supermaker

Created Time :2016/4/1 20:26:51

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6000 + 66;

struct Node

{

int to, nxt, c, f, cost;

};

Node edge[maxn*6];

int head[maxn], edgelen;

void Init ()

{

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

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

edgelen = 0;

}

void AddEdge (int cost, int u, int v, int w, int rw = 0)

{

edge[edgelen].to = v, edge[edgelen].c = w, edge[edgelen].f = 0;

edge[edgelen].cost = cost, edge[edgelen].nxt = head[u], head[u] = edgelen++;

edge[edgelen].to = u, edge[edgelen].c = rw, edge[edgelen].f = 0;

edge[edgelen].cost = -cost, edge[edgelen].nxt = head[v], head[v] = edgelen++;

}

int dis[maxn], cnt[maxn], inq[maxn], par[maxn];

int N;

bool spfa (int s, int e)

{

for (int i = 0; i <= N; i++)

{

dis[i] = INF;

inq[i] = cnt[i] = 0;

par[i] = -1;

}

dis[s] = 0;

queue <int> qu;

qu.push (s);

inq[s]++, cnt[s]++;

while (!qu.empty ())

{

int u = qu.front (); qu.pop (); inq[u]--;

if (cnt[u] > N)

{

DB ("hi");

return false;

}

for (int i = head[u]; i != -1; i = edge[i].nxt)

{

int v = edge[i].to;

if (edge[i].c > edge[i].f && dis[u] < INF && dis[v] > dis[u] + edge[i].cost)

{

dis[v] = dis[u] + edge[i].cost;

par[v] = i;

if (!inq[v])

{

qu.push (v);

inq[v]++, cnt[v]++;

}

if (par[e] == -1) return false;

return true;

}

int allcost;

int MinCostMaxFlow (int s, int e)

{

int res = 0;

allcost = 0;

while (spfa (s, e))

{

int minval = INF;

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

minval = min (minval, edge[i].c - edge[i].f);

for (int i = par[e]; i != -1; i = par[edge[i^1].to])

{

edge[i].f += minval;

edge[i^1].f -= minval;

allcost += edge[i].cost * minval;

}

res += minval;

//DB (res);

}

return res;

}

int g[66][66];

int main()

{

//CFF;

//CPPFF;

int n, k;

while (scanf ("%d%d", &n, &k) != EOF)

{

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

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

Init ();

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

{

int u = (i - 1) * n + j;

AddEdge (-g[i][j], u, u + n * n, 1);

AddEdge (0, u, u + n * n, k - 1);

if (i + 1 <= n)

AddEdge (0, u + n * n, u + n, k);

if (j + 1 <= n)

AddEdge (0, u + n * n, u + 1, k);

//DB (u), DB (u + n * n);

}

AddEdge (0, 0, 1, k);

AddEdge (0, 2 * n * n, 2 * n * n + 1, k);

N = 2 * n * n + 2;

MinCostMaxFlow (0, 2 * n * n + 1);

printf ("%d\n", -allcost);

}

return 0;

}

超客的水墨烟雨

poj3422

分类目录

标签云

书签

近期评论

2016年4月
一	二	三	四	五	六	日
« 3月				2月 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30