题解 - P2045 方格取数加强版

· · 个人记录 

题目描述
给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入输出格式
输入格式：
第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式：
一个数,为最大和

输入输出样例
输入样例#1： 
3 1
1 2 3
0 2 1
1 4 2
输出样例#1： 
11
说明
每个格子中的数不超过1000

网络流总能干一些奇奇怪怪的东西。。。

总结一下，比如要求次数，有方向性的东西。。。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int S,T,ans=0,n,bi=1,k,fl[100005],head[100005],nex[100005],go[100005],w[100005],d[100005],dis[100005],pre[100005],vis[100005],last[100005];
void add(int x,int y,int v,int dd)
{
    nex[++bi]=head[x];
    head[x]=bi;
    w[bi]=v;
    d[bi]=dd;
    go[bi]=y;
}
bool spfa()
{
    memset(dis,0x7f,sizeof(dis));
    memset(fl,0x7f,sizeof(fl));
    memset(vis,0,sizeof(vis));
    queue <int> q;
    pre[T]=-1;
    dis[S]=0;
    vis[S]=-1;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();
    //  cout<<u<<endl;
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=nex[i])
        {
            int v=go[i];
            if(w[i]>0&&dis[v]>dis[u]+d[i])
            {
                dis[v]=dis[u]+d[i];
                pre[v]=u;
                last[v]=i;
                fl[v]=min(fl[u],w[i]);
                if(!vis[v])
                {
                    vis[v]=-1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[T]==-1) return 0;
    return 1;
}
int num(int i,int j)//实用小技巧
{
    return 2*((i-1)*n+j);
}
int main()
{
    S=0;
    cin>>n>>k;
    T=n*n*2+1;//每个点分裂成两个    
    add(0,num(1,1)-1,k,0);//因为可以走k次，故流量为k
    add(num(1,1)-1,0,0,0);
    add(num(n,n),T,k,0);//超级汇点
    add(T,num(n,n),0,0);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        int x;
        cin>>x;
        x=-x;
        add(num(i,j)-1,num(i,j),1,x);//自己跟自己连一条流量为1，费用为x的边，保证流过一次，费用+；
        add(num(i,j),num(i,j)-1,0,-x);
        add(num(i,j)-1,num(i,j),1e9+7,0);//再连一条联通就行的边
        add(num(i,j),num(i,j)-1,0,0);
        if(i!=1)
        {
            add(num(i-1,j),num(i,j)-1,1e9,0);//联通即可
            add(num(i,j)-1,num(i-1,j),0,0);     
        }
        if(j!=1)
        {
            add(num(i,j-1),num(i,j)-1,1e9+7,0);//联通即可
            add(num(i,j)-1,num(i,j-1),0,0);
        }

    }

    while(spfa())//板子
    {
        ans+=(fl[T]*dis[T]);
        int now=T;
        while(now!=S)
        {
            w[last[now]]-=fl[T];
            w[last[now]^1]+=fl[T];
            now=pre[now];
        }
    }
    cout<<-ans<<endl;//我们是取反后跑最小费用流，相当于最大费用流，所以输出要取反
    return 0;      
}