HDU 4862

Jump

最小费用最大流。很经典的网络流建图。

Jump

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 189 Accepted Submission(s): 63

Problem Description

There are n*m grids, each grid contains a number, ranging from 0-9. Your initial energy is zero. You can play up to K times the game, every time you can choose any one of the grid as a starting point (but not traveled before) then you can choose a grid on the right or below the current grid to jump, but it has not traveled before. Every time you can jump as many times as you want, as long as you do not violate rules. If you are from (x1, y1) to (x2, y2), then you consume |x1-x2|+|y1-y2|-1 energies. Energy can be negative. However, in a jump, if you start position and end position has same numbers S, then you can increase the energy value by S. Give me the maximum energy you can get. Notice that you have to go each grid exactly once and you don’t have to play exactly K times.

Input

The first line is an integer T, stands for the number of the text cases. Then T cases followed and each case begin with three numbers N, M and K. Means there are N rows and M columns, you have K times to play. Then N lines follow, each line is a string which is made up by M numbers. The grids only contain numbers from 0 to 9. (T<=100, N<=10，M<=10，K<=100)

Output

Each case, The first you should output “Case x : ”,(x starting at 1),then output The maximum number of energy value you can get. If you can’t reach every grid in no more than K times, just output -1.

Sample Input

5 1 5 1 91929 1 5 2 91929 1 5 3 91929 3 3 3 333 333 333 3 3 2 333 333 333

Sample Output

Case 1 : 0 Case 2 : 15 Case 3 : 16 Case 4 : 18 Case 5 : -1

Author

FZU

Source

2014 Multi-University Training Contest 1

建图方法： 左右各n*m个点。加一个源点和一个汇点。 源点向左侧的每一个点连一条流量为1，费用为0的边。 右侧点连一条流量为1，费用为0的边到汇点。 如果左侧点的点，可以转移的话，对应连一条左侧点到右侧点的边，一步到达。 费用是消耗的费用-获得的费用。   再加一个点，起点到这个点连流量为1，费用为0的边。这个点向右侧的点连一条流量为1，费用为0的边。。   如果非满流，则不满足。 否则最小费用相反数就是最大收益。

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

Author        :kuangbin

Created Time  :2014/7/22 22:53:24

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校1\2014 Multi-University Training Contest 1（标程+数据）\多校第一场（标程+数据）\HDU4862.cpp

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

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 1010;

const int MAXM = 10010;

const int INF = 0x3f3f3f3f;

struct Edge

{

	int to,next,cap,flow,cost;

}edge[MAXM];

int head[MAXN],tol;

int pre[MAXN],dis[MAXN];

bool vis[MAXN];

int N;

void init(int n)

{

	N = n;

	tol = 0;

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

}

void addedge(int u,int v,int cap,int cost)

{

	edge[tol].to = v;

	edge[tol].cap = cap;

	edge[tol].cost = cost;

	edge[tol].flow = 0;

	edge[tol].next = head[u];

	head[u] = tol++;

	edge[tol].to = u;

	edge[tol].cap = 0;

	edge[tol].cost = -cost;

	edge[tol].flow = 0;

	edge[tol].next = head[v];

	head[v] = tol++;

}

bool spfa(int s,int t)

{

	queue<int>q;

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

	{

		dis[i] = INF;

		vis[i] = false;

		pre[i] = -1;

	}

	dis[s] = 0;

	vis[s] = true;

	q.push(s);

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

		vis[u] = false;

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

		{

			int v = edge[i].to;

			if(edge[i].cap > edge[i].flow && 

					dis[v] > dis[u] +edge[i].cost)

			{

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

				pre[v] = i;

				if(!vis[v])

				{

					vis[v] = true;

					q.push(v);

				}

			}

		}

	}

	if(pre[t] == -1)return false;

	else return true;

}

int minCostMaxflow(int s,int t,int &cost)

{

	int flow = 0;

	cost = 0;

	while(spfa(s,t))

	{

		int Min = INF;

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

		{

			if(Min > edge[i].cap - edge[i].flow)

				Min = edge[i].cap - edge[i].flow;

		}

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

		{

			edge[i].flow += Min;

			edge[i^1].flow -= Min;

			cost += edge[i].cost*Min;

		}

		flow += Min;

	}

	return flow;

}

int n,m,k;

char str[12][12];

void solve()

{

	init(2*n*m + 3);

	int start = 2*n*m;

	int end = 2*n*m+2;

	addedge(start,start+1,k,0);

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

		for(int j = 0;j < m;j++)

		{

			addedge(start,2(im+j),1,0);

			addedge(2(im+j)+1,end,1,0);

			addedge(start+1,2(im+j)+1,1,0);

			for(int y = j+1;y < m;y++)

			{

				if(str[i][y] == str[i][j])

					addedge(2(i*m+j),2*(im+y)+1,1,-(str[i][j]-'0')+y-j-1);

				else addedge(2(i*m+j),2*(im+y)+1,1,y-j-1);

			}

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

			{

				if(str[x][j] == str[i][j])

					addedge(2(i*m+j),2*(xm+j)+1,1,-(str[i][j]-'0')+x-i-1);

				else addedge(2(i*m+j),2*(xm+j)+1,1,x-i-1);

			}

		}

	int cost;

	int flow = minCostMaxflow(start,end,cost);

	if(flow != n*m)printf("-1\n");

	else printf("%d\n",-cost);

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

	int T;

	scanf("%d",&T);

	int iCase = 0;

    while(T--)

	{

		iCase++;

		scanf("%d%d%d",&n,&m,&k);

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

			scanf("%s",str[i]);

		printf("Case %d : ",iCase);

		solve();

	}

    return 0;

}