【P2405】方格取数问题加强版(费用流)

考虑如何建图。还是老样子先拆点，然后把每两个点之间连接两条边，一条流量为1，费用为-点权，处理是否走这个点。一条流量无限，没有费用，因为哪怕一个点选过了，它的地方还是可以重复走过去的。然后把经由一个点能到达的另一个点连边。因为要走k次，所以由s向1号点入点连边，n号点出点向t连边，流量为k，费用为0。然后一边最小费用最大流板子即可。然后发现这些个题解里没有用原始对偶来实现的，所以弱弱的拿出自己代码，勉强还是能在最优解第一页里的，膜拜那些50ms都不到就跑完的dalao们。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define ll long long

#define rp (i-1)*n+j

#define cp (i-1)*n+j+n*n

#define inf 50000000

#define re register

using namespace std;

struct po

{

    int from,to,dis,nxt,w;

}edge[];

int head[],cur[],dep[],n,m,s,t,u,num=-,x,y,l,tot,sum,k;

int dis[],b[],xb[],flow[],a[][];

inline int read()

{

    int x=,c=;

    char ch=' ';

    while((ch>''||ch<'')&&ch!='-')ch=getchar();

    while(ch=='-')c*=-,ch=getchar();

    while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();

    return x*c;

}

inline void add_edge(int from,int to,int w,int dis)

{

    edge[++num].nxt=head[from];

    edge[num].to=to;

    edge[num].w=w;

    edge[num].dis=dis;

    head[from]=num;

}

inline void add(int from,int to,int w,int dis)

{

    add_edge(from,to,w,dis);

    add_edge(to,from,,-dis);

}

inline bool spfa()

{

    memset(b,,sizeof(b));

    memset(dis,,sizeof(dis));

    deque<int> q;

    while(!q.empty())

    q.pop_back();

    dis[t]=;b[t]=;

    q.push_back(t);

    while(!q.empty())

    {

        int u=q.front();

        q.pop_front();

        b[u]=;

        for(re int i=head[u];i!=-;i=edge[i].nxt)

        {

            int v=edge[i].to;

            if(edge[i^].w>&&dis[v]>dis[u]-edge[i].dis)

            {

                dis[v]=dis[u]-edge[i].dis;

                if(!b[v])

                {

                    b[v]=;

                    if(!q.empty()&&dis[v]<dis[q.front()])

                    q.push_front(v);

                    else

                    q.push_back(v);

                }

            }

        }

    }

    return dis[s]<inf;

}

inline int dfs(int u,int low)

{

    if(u==t)

    {

        b[t]=;

        return low;

    }

    int diss=;

    b[u]=;

    for(re int i=head[u];i!=-;i=edge[i].nxt)

    {

        int v=edge[i].to;

        if(!b[v]&&edge[i].w!=&&dis[v]==dis[u]-edge[i].dis)

        {

            int check=dfs(v,min(low,edge[i].w));

            if(check>)

            {

                tot+=check*edge[i].dis;

                low-=check;

                diss+=check;

                edge[i].w-=check;

                edge[i^].w+=check;

                if(low==) break;

            }

        }

    }

    return diss;

}

inline void max_flow()

{

    int ans=;

    while(spfa())

    {

        b[t]=;

        while(b[t]==)

        {

            memset(b,,sizeof(b));

            ans=dfs(s,inf);

        }

    }

}

int main()

{

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

    n=read();k=read();

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

     for(re int j=;j<=n;j++)

        a[i][j]=read();

    s=;t=n*n*+;

    add(s,,k,);add(n*n*,t,k,);

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

     for(re int j=;j<=n;j++)

     {

        add(rp,cp,,-a[i][j]);

        add(rp,cp,inf,);

        if(i<n)

        add(cp,rp+n,inf,);

        if(j<n)

        add(cp,rp+,inf,);

     }

    max_flow();

    cout<<-tot;

}

巴特西

【P2405】方格取数问题加强版(费用流)

最新文章

热门文章