首页 > 代码库 > hdu 2686 Matrix【最大费用流】

hdu 2686 Matrix【最大费用流】

2024-08-04 16:18:17   220人阅读

Matrix

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1792    Accepted Submission(s): 958


Problem Description
Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix.
Every time yifenfei should to do is that choose a detour which frome the top left point to the bottom right point and than back to the top left point with the maximal values of sum integers that area of Matrix yifenfei choose. But from the top to the bottom can only choose right and down, from the bottom to the top can only choose left and up. And yifenfei can not pass the same area of the Matrix except the start and end.
 

Input
The input contains multiple test cases.
Each case first line given the integer n (2<n<30)
Than n lines,each line include n positive integers.(<100)
 

Output
For each test case output the maximal values yifenfei can get.
 

Sample Input
2
10 3
5 10
3
10 3 3
2 5 3
6 7 10
5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
 

Sample Output
28
46
80

分析：题意是给出一个矩阵，从（0，0）点到（n-1，n-1）点到（0，0）点使这条路径节点权值之和最大，且从（0，0）到（n-1，n-1）点
只能往右或下走，而回路则相反，每个节点只能走一次。因为每个节点走一次，所以要拆点，容量为1，花费为0，前一部分与s连接，后一部分与
t连接。另外还有方向的规则，我们可以这样想：从s-t-s，这一圈相当于跑两遍s-t，只不过多跑了一个s节点和t节点，最后减去即可，如果这样
那我们建边时指、只向每个节点右和下建，因为我们只是从s-t，而所谓的t-s只能向左和上跑，等价与s-t向右和下跑，这样就差不多解决了。
跑最大费流模版可以直接写最小费用流的，只要加边时把cost改成-cost，在把costflow改成-costflow就可以了。
代码示例：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#define Min(a,b) a<b?a:b
#define maxn 40000+10
#define maxm 20000+10
#define inf 0xffffff
using namespace std;
typedef struct
{
    int from,to,next;
    int val,cost;
}node;
node E[maxn];
int head[maxm],dis[maxm],visit[maxm],pre[maxm],pos[maxm],cnt;
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void add(int from,int to,int val,int cost)
{
    E[cnt].from=from,E[cnt].to=to,E[cnt].val=val,E[cnt].cost=cost;
    E[cnt].next=head[from],head[from]=cnt++;
    E[cnt].from=to,E[cnt].to=from,E[cnt].val=0,E[cnt].cost=-cost;
    E[cnt].next=head[to],head[to]=cnt++;
}
bool spfa(int s,int t,int n)
{
    int to,val,cost;
    for(int i=0;i<=n;i++)
    {
        dis[i]=inf,visit[i]=0,pre[i]=-1;
    }
    dis[s]=0,visit[s]=1,pre[s]=s;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop();
        visit[k]=0;
        for(int i=head[k];i!=-1;i=E[i].next)
        {
            to=E[i].to;
            val=E[i].val;
            cost=E[i].cost;
            if(val>0&&dis[k]+cost<dis[to])
            {
                dis[to]=dis[k]+cost;
                pre[to]=k;
                pos[to]=i;
                if(visit[to])
                continue;
                visit[to]=1;
                Q.push(to);
            }
        }
    }
    if(pre[t]!=-1&&dis[t]<inf)
    return true;
    return false;
}
int MaxCostFlow(int s,int t,int n)
{
    int costflow=0,netflow=0,min;
    while(spfa(s,t,n))
    {
        min=inf;
        for(int i=t;i!=s;i=pre[i])
        {
            min=Min(min,E[pos[i]].val);
        }
        netflow+=min;
        costflow+=min*dis[t];
        for(int i=t;i!=s;i=pre[i])
        {
            E[pos[i]].val-=min;
            E[pos[i]^1].val+=min;
        }
    }
    return -costflow;
}
int main()
{
    int s,t,n,x,sum;
    while(~scanf("%d",&n))
    {
        init();
        sum=0;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            scanf("%d",&x);
            if((i==0&&j==0)||(i==n-1&&j==n-1))
            {
                add(i*n+j,i*n+j+n*n,2,-x);
                sum+=x;
            }
            else
            {
                add(i*n+j,i*n+j+n*n,1,-x);
            }
            if(i+1<n)
            {
                add(i*n+j+n*n,(i+1)*n+j,1,0);
            }
            if(j+1<n)
            {
                add(i*n+j+n*n,i*n+j+1,1,0);
            }
        }
        s=2*n*n+1,t=2*n*n+2;
        add(s,0,2,0);
        add(2*n*n-1,t,2,0);
        printf("%d\n",MaxCostFlow(s,t,t+10)-sum);
}
return 0;
}

hdu 2686 Matrix【最大费用流】


联系
我们