ネットワーク料金フロー-最小kパスオーバーライド

6814 ワード

ネットワーク

多校リーグ第1戦(hdu 4862)
Jump
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 644 Accepted Submission(s): 275
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

Sample Output


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

1つのn行m列の行列を与えて、各座標の上ですべて1つの重み値があって、最大でk回歩くことができて(k歩ではありませんことに注意して)、毎回歩くのは任意に起点(必ず歩いたことがない点)を選択することができて、それから右あるいは下へ任意の歩数を歩くことができて、各歩は任意の格数を越えることができて、前提はテーマの制限条件を満たすので、歩くたびに消費されるエネルギーは2座標のマンハッタン距離-1で、歩く現在の点の重み値を加えて前のステップの重み値と同じように、この重み値のエネルギーを得ることができて、k回の歩行内で、1格ごとに歩いて1回だけ歩いて、最大でどれだけのエネルギーを得ることができます:このテーマは主に図を建てるので、k回の建図はとても巧みです.
公式の問題解:
最小Kパスオーバーライドのモデルは、費用フローまたはKMアルゴリズムで解決し、二部図を構築し、X部にN*M個のノードがあり、ソース点がX部の各ノードに1辺ずつ接続され、流量1、費用0、Y部にN*M個のノードがあり、各ノードが合流点に1辺ずつ接続され、流量1、費用0があり、X部のノードxが一歩以内にY部のノードyに到達できれば、辺x->yまで接続され、費用はx格子からy格子までの費用エネルギーから差し引いたエネルギーであり、流量1、さらにX部に新しいノードを追加し、任意のノードからK回出発してもよいことを示し、ソース点からその辺に接続し、費用0、流量K、この点からY部に各点に接続し、費用0、流量1、最もこの図は最小費用最大流を走り、満流が解であれば、逆は存在しない.最小費用の逆数が得られる最大エネルギーです
このように考えることができ、まず、x部内のy部に到達可能な点建辺の二分図を確立する.まず、この2部図の最小パスオーバーライド=ノード総数−最大ストリームを求める.(最小パスオーバーライド:最小パスですべてのノードをオーバーライドし、各ノードは1つのパスしか使用できません)、k値が最小パス数より小さい場合、k回以内にタスクを完了することはできません.
従って、このように図面を作成した後に元の最大流+kを求め、最大流+kプログラム;

#include"stdio.h"
#include"string.h"
#include"iostream"
#include"map"
#include"string"
#include"queue"
#include"stdlib.h"
#include"math.h"
#define M 333
#define eps 1e-10
#define inf 1000000000
#define mod 2333333
using namespace std;
struct node
{
    int u,v,w,cost,next;
}edge[M*M*3];
int t,head[M],dis[M],use[M],pre[M],Max_flow,Min_cost,top[M],q[M],work[M];
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w,int cost)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].w=w;
    edge[t].cost=cost;
    edge[t].next=head[u];
    head[u]=t++;

    edge[t].u=v;
    edge[t].v=u;
    edge[t].w=0;
    edge[t].cost=-cost;
    edge[t].next=head[v];
    head[v]=t++;
}
int min_flow(int S,int T)
{
    int ans=0;
    Max_flow=0;
    while(1)
    {
        int i;
        queue<int>q;
        for(i=0;i<=T+1;i++)
            dis[i]=inf;
        dis[S]=0;
        memset(use,0,sizeof(use));
        memset(pre,-1,sizeof(pre));
        q.push(S);
        while(!q.empty())
        {
            int u=q.front();
            use[u]=0;
            q.pop();
            for(i=head[u];i!=-1;i=edge[i].next)
            {
                int v=edge[i].v;
                if(edge[i].w&&dis[v]>dis[u]+edge[i].cost)
                {
                    dis[v]=dis[u]+edge[i].cost;
                    pre[v]=i;
                    if(!use[v])
                    {
                        use[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        if(dis[T]==inf)
            break;
        int Min=inf+1;
        for(i=pre[T];i!=-1;i=pre[edge[i].u])
        {
            Min=min(Min,edge[i].w);
        }
        for(i=pre[T];i!=-1;i=pre[edge[i].u])
        {
            edge[i].w-=Min;
            edge[i^1].w+=Min;
        }
        Max_flow+=Min;
        ans+=Min*dis[T];
    }
    return ans;
}
int num[22][22],mp[22][22];
char Mp[22][22];
int main()
{
    int T,kk=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,k,i,j,r;
        scanf("%d%d%d",&n,&m,&k);
        int cnt=0;
        init();
        for(i=1;i<=n;i++)
        {
            scanf("%s",Mp[i]);
            for(j=1;j<=m;j++)
            {
                mp[i][j]=Mp[i][j-1]-'0';
                num[i][j]=++cnt;
            }
        }
        for(i=1;i<=m*n;i++)
        {
            add(0,i,1,0);
            add(i+m*n,m*n*2+1,1,0);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                int Cost;
                for(r=j+1;r<=m;r++)
                {
                    if(mp[i][j]==mp[i][r])
                        Cost=r-j-1-mp[i][j];
                    else
                        Cost=r-j-1;
                    add(num[i][j],num[i][r]+m*n,1,Cost);
                }
                for(r=i+1;r<=n;r++)
                {
                    if(mp[i][j]==mp[r][j])
                        Cost=r-i-1-mp[i][j];
                    else
                        Cost=r-i-1;
                    add(num[i][j],num[r][j]+m*n,1,Cost);
                }
            }
        }
        for(i=n*m+1;i<=m*n*2;i++)
            add(m*n*2+2,i,1,0);
        add(0,m*n*2+2,k,0);
        Min_cost=min_flow(0,m*n*2+1);
        printf("Case %d : ",kk++);
        if(Max_flow!=n*m)
        {
            printf("-1
");
            continue;
        }
        printf("%d
",-Min_cost);
    }
}

JMFプレイヤー小例

フィルタを使用してSQL注入とサイト間スクリプト作成を解決