Matrix3

My Tags
  (Edit)
 
Source : bin3
 
Time limit : 5 sec
 
Memory limit : 64 M
Submitted : 302, Accepted : 74
Zhouguyue is a "당나귀 친구"and nowadays he likes traveling on an N * N matrix with a non-negative number in each grid, and each grid has a height.Zhouguyue starts his matrix travel with POINT = 0. For each travel, zhouguyue can land on any grid he wants with the help of bin3's helicopter, and then he can only move to ajacent grids whose height is less than his current height. Notice that when he is at the side of the matrix, he can also move out of the matrix. After he moves out of the matrix, he completes one travel. He adds the number in each grid he visited to POINT, and replaces it with zero. Now zhouguyue is wondering what is the maximum POINT he can obtain after he travels at most K times. Note the POINT is accumulative during the travels.

Input

The first line is a integer T indicating the number of test cases.T cases fllows. The first line of each case contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 50) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are non-negative integers and no more than 10000. The following N lines represents the height of each grid. The heghts are also non-negative integers.

Output

The maximum POINT zhouguyue can obtain after he travels at most K times.

Sample Input

1
3 2
1 2 3
3 2 1
2 4 2

3 5 3
2 1 0
1 2 3

Sample Output

17

제목:http://acm.hit.edu.cn/hoj/problem/view?id=2715
제목: 바로 하나의 행렬입니다. 매번 당신은 임의로 칸을 선택한 다음에 그와 인접한 칸보다 낮은 칸으로 뛰어갈 수 있습니다. 칸마다 점수가 있습니다. 연속적으로 k번으로 얻을 수 있는 점수와 최대치를 물어보세요...
분석: 뚜렷한 최대 비용 최대 흐름...먼저 반드시 점을 나누어야 한다. 각 칸을 두 점으로 나누어야 한다. 이 두 점 사이에는 두 개의 변, 한 개의 용량은 1이고 비용은 칸 점수의 반대수(최소 비용 흐름으로 전환), 다른 한 개의 변의 용량은 무한하다. 비용은 0(이하 변은 모두 이런 변)이다. 칸을 여러 번 통과할 수 있음을 나타낸다. 그 다음에 서로 인접한 칸에 대해 조건을 충족시키는 것도 한 개의 변, 주의점의 층을 연결해야 한다.그 다음에 세 개의 점, 하나의 환점을 허구하여 행렬 가장자리에 있는 칸에 그녀, 하나의 원점, 모든 칸, 하나의 총 원점, 하나의 원점이 연결되어 있다. 이 칸은 용량을 k로 요구하면 된다...
그리고 템플릿을...1Y
히트가 적은 것 같은데 내가 제일 빠르다--
코드:

#include<cstdio>
#include<iostream>
using namespace std;
const int mm=66666;
const int mn=5555;
const int oo=1e9;
int src,dest,node,edge;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int ver[mm],cost[mm],flow[mm],next[mm];
int head[mn],dis[mn],p[mn],q[mn];
int h[55][55];
bool vis[mn]={0};
void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0;i<node;++i)head[i]=-1;
    edge=0;
}
void addedge(int u,int v,int f,int c)
{
    ver[edge]=v,flow[edge]=f,cost[edge]=c,next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=0,cost[edge]=-c,next[edge]=head[v],head[v]=edge++;
}
bool Spfa()
{
    int i,u,v,l,r=0,tmp;
    for(i=0;i<node;++i)dis[i]=oo;
    dis[q[r++]=src]=0;
    p[src]=p[dest]=-1;
    for(l=0;l!=r;(++l==mn)?l=0:l)
        for(i=head[u=q[l]],vis[u]=0;i>=0;i=next[i])
            if(flow[i]&&dis[v=ver[i]]>(tmp=dis[u]+cost[i]))
            {
                dis[v]=tmp;
                p[v]=i^1;
                if(vis[v])continue;
                vis[q[r++]=v]=1;
                if(r==mn)r=0;
            }
    return p[dest]>-1;
}
int Spfaflow()
{
    int i,delta,ret=0;
    while(Spfa())
    {
        for(i=p[dest],delta=oo;i>=0;i=p[ver[i]])
            if(flow[i^1]<delta)delta=flow[i^1];
        for(i=p[dest];i>=0;i=p[ver[i]])
            flow[i]+=delta,flow[i^1]-=delta;
        ret-=delta*dis[dest];
    }
    return ret;
}
int main()
{
    int i,j,x,y,k,n,m,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        prepare(n*n*2+3,n*n*2+1,n*n*2+2);
        for(i=0;i<n;++i)
            for(j=1;j<=n;++j)
            {
                scanf("%d",&k);
                addedge(0,i*n+j,oo,0);
                addedge(i*n+j,n*n+i*n+j,1,-k);
                addedge(i*n+j,n*n+i*n+j,oo,0);
            }
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                scanf("%d",&h[i][j]);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                for(k=0;k<4;++k)
                {
                    x=i+dx[k];
                    y=j+dy[k];
                    if(x<1||x>n||y<1||y>n||h[x][y]>=h[i][j])continue;
                    addedge(n*n+i*n-n+j,x*n-n+y,oo,0);
                }
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                if(i==1||j==1||i==n||j==n)
                    addedge(n*n+n*i-n+j,dest,oo,0);
        addedge(src,0,m,0);
        printf("%d
",Spfaflow());
    }
    return 0;
}