题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3376
题意:给出一个矩阵,从(1,1)走到(n,n),然后再从(n,n)走到(1,1),每个点只能走一次,除了(n,n)点。求最大值
题目分类:最大流
题目代码:
#include<bits/stdc++.h> using namespace std; const int MAXN=610*610*2+2; const int inf=1<<29; int pre[MAXN]; // pre[v] = k:在增广路上,到达点v的边的编号为k int dis[MAXN]; // dis[u] = d:从起点s到点u的路径长为d int vis[MAXN]; // inq[u]:点u是否在队列中 int path[MAXN]; int head[MAXN]; int NE,tot,ans,max_flow,mapp[666][666]; struct node { int u,v,cap,cost,next; } Edge[MAXN<<2]; void addEdge(int u,int v,int cap,int cost) { Edge[NE].u=u; Edge[NE].v=v; Edge[NE].cap=cap; Edge[NE].cost=cost; Edge[NE].next=head[u]; head[u]=NE++; Edge[NE].v=u; Edge[NE].u=v; Edge[NE].cap=0; Edge[NE].cost=-cost; Edge[NE].next=head[v]; head[v]=NE++; } int SPFA(int s,int t) // 源点为0,汇点为sink。 { int i; for(i=s;i<=t;i++) dis[i]=inf; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); dis[s] = 0; queue<int>q; q.push(s); vis[s] =1; while(!q.empty()) // 这里最好用队列,有广搜的意思,堆栈像深搜。 { int u =q.front(); q.pop(); for(i=head[u]; i!=-1;i=Edge[i].next) { int v=Edge[i].v; if(Edge[i].cap >0&& dis[v]>dis[u]+Edge[i].cost) { dis[v] = dis[u] + Edge[i].cost; pre[v] = u; path[v]=i; if(!vis[v]) { vis[v] =1; q.push(v); } } } vis[u] =0; } if(pre[t]==-1) return 0; return 1; } void end(int s,int t) { int u, sum = inf; for(u=t; u!=s; u=pre[u]) { sum = min(sum,Edge[path[u]].cap); } max_flow+=sum; for(u = t; u != s; u=pre[u]) { Edge[path[u]].cap -= sum; Edge[path[u]^1].cap += sum; ans += sum*Edge[path[u]].cost; // cost记录的为单位流量费用,必须得乘以流量。 } } int main() { int i,j,n,s,t; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); NE=ans=max_flow=s=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&mapp[i][j]); } } int k=n*n; t=2*k+1; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { addEdge(j+(i-1)*n,k+j+(i-1)*n,1,-mapp[i][j]); if(j!=n) addEdge(k+j+(i-1)*n,j+1+(i-1)*n,inf,0);///右边 if(i!=n) addEdge(k+j+(i-1)*n,i*n+j,inf,0);///下边 } } addEdge(s,1,2,0); addEdge(1,k+1,1,0); addEdge(2*k,t,2,0); addEdge(k,2*k,1,0); while(SPFA(s,t)) { end(s,t); } printf("%d ",-ans); } return 0; }