问题 D: 探 寻 宝 藏
时间限制: 1 Sec 内存限制: 128 MB题目描述
传说HMH大沙漠中有一个M*N迷宫，里面藏有许多宝物。某天，Dr.Kong找到了迷宫的地图，他发现迷宫内处处有宝物，最珍贵的宝物就藏在右下角，迷宫的进出口在左上角。当然，迷宫中的通路不是平坦的，到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。
但机器人卡多从左上角走到右下角时，只会向下走或者向右走。从右下角往回走到左上角时，只会向上走或者向左走，而且卡多不走回头路。（即：一个点最多经过一次）。当然卡多顺手也拿走沿路的每个宝物。
Dr.Kong希望他的机器人卡多尽量多地带出宝物。请你编写程序，帮助Dr.Kong计算一下，卡多最多能带出多少宝物。
输入
第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: M N
第2~M+1行： Ai1 Ai2 ……AiN (i=1,…..,m)
2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)
所有数据都是整数。 数据之间有一个空格。
输出
对于每组测试数据，输出一行：机器人卡多携带出最多价值的宝物数
样例输入
2
2 3
0 10 10
10 10 80
3 3
0 3 9
2 8 5
5 7 100
样例输出
120
134
//直接最小费用最大流模板~
代码如下：
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
#define N 5005
#define INF 0x3fffffff
struct node
{
int u,v;
int w,k;
int next;
}edge[10*N];
int idx,head[N];
void Init(){ idx=0; memset(head,-1,sizeof(head)); }
void Addedge(int x,int y,int w,int k)
{
edge[idx].u=x; edge[idx].v=y;
edge[idx].w=w; edge[idx].k=k;
edge[idx].next = head[x];
head[x] = idx++;
}
void Add(int x,int y,int w,int k)
{
Addedge(x,y,w,k);
Addedge(y,x,-w,0);
}
int ans;
bool mark[N];
int dis[N],route[N];
void SPFA_Init(int start,int end)
{
for(int i=0; i<=end; ++i)
dis[i] = INF;
memset(mark,false,sizeof(mark));
memset(route,-1,sizeof(route));
dis[start] = 0;
mark[start] = true;
}
int SPFA(int start,int end)
{
int i;
int x,y;
SPFA_Init(start,end);
queue<int> q;
q.push(start);
while(!q.empty())
{
x = q.front();
q.pop();
for(i=head[x]; i!=-1; i=edge[i].next)
{
y = edge[i].v;
if(edge[i].k && dis[y]>dis[x]+edge[i].w)
{
dis[y]=dis[x]+edge[i].w;
route[y] = i;
if(!mark[y])
{
mark[y]=true;
q.push(y);
}
}
}
mark[x]=false;
}
if(route[end]==-1) return 0;
return 1;
}
void EK(int start,int end)
{
int x,y;
y=route[end];
while(y!=-1)
{
x = y^1;
edge[y].k--;
edge[x].k++;
ans += edge[y].w;
y = route[edge[y].u];
}
}
int main()
{
int T;
int m,n;
int i,j;
int x,k,w;
int start,end;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
Init();
k = n*m;
start = 0;
end = 2*n*m+1;
Add(start,1,0,2); //起点start和点1建两条边
Add(1,k+1,0,1); //点1和点k+1再加一条边
for(i=1; i<=m; ++i)
{
for(j=1; j<=n; ++j)
{
x = j+(i-1)*n;
scanf("%d",&w);
Add(x,x+k,-w,1); //题目要求最大值，故取反
if(i!=m) Add(x+k,x+n,0,INF);
if(j!=n) Add(x+k,x+1,0,INF);
}
}
Add(2*k,end,0,2); //终点end和点2*k建两条边
Add(k,2*k,0,1); //点k和点2*k再加一条边
ans = 0;
while(SPFA(start,end)) //最小费用最大流算法
EK(start,end);
printf("%d
",-ans);
}
return 0;
}