[poj] 3422 Kaka's Matrix Travels || 最小费用最大流

原题

给一个N*N的方阵，从[1,1]到[n,n]走K次，走过每个方格加上上面的数，然后这个格上面的数变为0。求可取得的最大的值。

要求最大值，所以把边权全为负跑最小费用即可。因为只有第一次经过该点的时候会得到价值，所以我们将一个点拆为两个，连一条容量为1费用为负权的边和一条容量为k-1费用为0的边。然后和右和下的点连边为容量为k，费用为0的边。跑费用流即可。

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

#define N 5010

#define inf 0x3f3f3f3f

using namespace std;

int n,m,head[N],dis[N],cur[N],ans,cnt=2,s,t,ANS,T,a[55][55],k;

queue <int> q;

bool vis[N];

struct hhh

{

    int to,next,w,cost;

}edge[N*N];

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') fu=-1,j=getchar();

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void add(int u,int v,int w,int c)

{

    edge[cnt].to=v;

    edge[cnt].w=w;

    edge[cnt].next=head[u];

    edge[cnt].cost=c;

    head[u]=cnt++;

}

void addEdge(int u,int v,int w,int c)

{

    add(u,v,w,c);

    add(v,u,0,-c);

}

bool bfs()

{

    for (int i=s;i<=t;i++)

	vis[i]=0,cur[i]=head[i],dis[i]=inf;

    q.push(s);

    dis[s]=0;

    vis[s]=1;

    while(!q.empty())

    {

	int r=q.front();

	q.pop();

	vis[r]=0;

	for (int i=head[r],v;i;i=edge[i].next)

	{

	    v=edge[i].to;

	    if (edge[i].w>0 && dis[r]+edge[i].cost<dis[v])

	    {

		dis[v]=dis[r]+edge[i].cost;

		if (!vis[v])

		{

		    vis[v]=1;

		    q.push(v);

		}

	    }

	}

    }

    return dis[t]!=inf;

}

int dfs(int x,int f)

{

    if (x==t) return ANS+=f*dis[t],f;

    int ha=0,now;

    vis[x]=1;

    for (int &i=cur[x],v;i;i=edge[i].next)

    {

	v=edge[i].to;

	if (vis[v]) continue;

	if (edge[i].w>0 && dis[v]==dis[x]+edge[i].cost)

	{

	    now=dfs(v,min(f-ha,edge[i].w));

	    if (now)

	    {

		ha+=now;

		edge[i].w-=now;

		edge[i^1].w+=now;

	    }

	}

	if (ha==f) return ha;

    }

    return ha;

}

int main()

{

    n=read();

    k=read();

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

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

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

    s=0;

    t=2*n*n+1;

    addEdge(s,1,k,0);

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

	for (int j=1,p;j<=n;j++)

	{

	    p=n*(i-1)+j;

	    addEdge(p,p+n*n,1,-a[i][j]);

	    addEdge(p,p+n*n,k-1,0);

	    if (i<n) addEdge(p+n*n,p+n,k,0);

	    if (j<n) addEdge(p+n*n,p+1,k,0);

	}

    addEdge(2*n*n,t,k,0);

    while (bfs()) ans+=dfs(s,inf);

    printf("%d",-ANS);

    return 0;

}

巴特西

[poj] 3422 Kaka's Matrix Travels || 最小费用最大流

原题

最新文章

热门文章