首页 > 代码库 > HDU 3376

HDU 3376

2024-07-14 21:54:17   214人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3376

题意：一个矩阵，每个点有价值，起点左上角终点右下角，每次只能走当前点的下一点或右一点，从起点走到终点，再从终点回到起点，走的点不能重复，问能取到的最大价值

用费用流做

建图：

拆点（保证每个点只取1次），除了起点和终点其他点拆点的容量是1，起点终点容量是2（走来回）

可以加源点汇点，最后答案刨去一次起点终点的价值（因为费用流会加两次），也可以不加，最后自己加上起点终点的价值

#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std ;const int INF=0xfffffff ;struct node{    int s,t,cap,cost,nxt ;}e[4000005] ;int sumflow ;int n,m,cnt,head[1000005],vis[1000005],dis[1000005],pre[1000005] ;void add(int s,int t,int cap,int cost){    e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].cost=cost ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;    e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].cost=-cost ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;}int spfa(int s,int t,int N){    for(int i=0 ;i<=N ;i++)        dis[i]=INF ;    dis[s]=0 ;    memset(vis,0,sizeof(vis)) ;    memset(pre,-1,sizeof(pre)) ;    vis[s]=1 ;    queue <int> q ;    q.push(s) ;    while(!q.empty())    {        int u=q.front() ;        q.pop() ;        vis[u]=0 ;        for(int i=head[u] ;i!=-1 ;i=e[i].nxt)        {            int tt=e[i].t ;            if(e[i].cap && dis[tt]>dis[u]+e[i].cost)            {                dis[tt]=dis[u]+e[i].cost ;                pre[tt]=i ;                if(!vis[tt])                {                    vis[tt]=1 ;                    q.push(tt) ;                }            }        }    }    if(dis[t]==INF)return 0 ;    return 1 ;}int MCMF(int s,int t,int N){    int flow,minflow,mincost ;    mincost=flow=0 ;    while(spfa(s,t,N))                                                    {        minflow=INF ;        for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s])            minflow=min(minflow,e[i].cap) ;        flow+=minflow ;        for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s])        {            e[i].cap-=minflow ;            e[i^1].cap+=minflow ;        }        mincost+=dis[t]*minflow ;    }    sumflow=flow ;//最大流     return mincost ;}int num[605][605],M[605][605] ;int main(){    while(~scanf("%d",&n))    {        cnt=0 ;        memset(head,-1,sizeof(head)) ;        int S=0 ;        int T=2*n*n+1 ;        int ct=1 ;        for(int i=1 ;i<=n ;i++)            for(int j=1 ;j<=n ;j++)            {                scanf("%d",&M[i][j]) ;                num[i][j]=ct++ ;            }           add(S,1,2,0) ;           add(n*n*2,T,2,0) ;          for(int i=1 ;i<=n ;i++)          {              for(int j=1 ;j<=n ;j++)              {                  if(num[i][j]==1)add(num[i][j],num[i][j]+n*n,2,-M[i][j]) ;                  else if(num[i][j]==n*n)add(num[i][j],num[i][j]+n*n,2,-M[i][j]) ;                  else add(num[i][j],num[i][j]+n*n,1,-M[i][j]) ;                  if(i<n)add(num[i][j]+n*n,num[i][j]+n,1,0) ;                  if(j<n)add(num[i][j]+n*n,num[i][j]+1,1,0) ;              }          }          printf("%d\n",-(MCMF(S,T,T+1)+M[1][1]+M[n][n])) ;    }    return 0 ;}
View Code

 


联系
我们