HDU 2686 Matrix(费用流)
http://acm.hdu.edu.cn/showproblem.php?pid=2686
题意:
有一个n*n的矩阵,矩阵的格子中每个都有一个正数.现在你要从左上角走到右下角去,然后在从右下角回到左上角.过程中除了左上角和右下角外,任意网格最多走一次,且要求你所走过的所有网格的权值和最大,为最大值是多少?
分析:
因为要求网格的权值和,所以我们把(除了左上角和右下角外)每个网格点都分成i和i+n*n两个点,且连边(i, i+n*n, 1, -w).
注意这里权值取负.
而且我们要找一条去和一条回的不相交的路,其实就是要找从左上角到右下角的两条不相交的路径.(想想是不是) 此时我们只要把左上角作为源点s,右下角作为汇点t,求一次最小费用最大流即可.
如果i节点的右边或下面正好是j节点,那么有边(i+n*n,j,1,0) 这里要注意判断边界情况.(如果i==s源点,那么它到后继的边与普通点到后继的边不同,具体看代码)
因为本题是网格,所以一定有解,最终我们求得的最小费用的绝对值就是我们要求的最大权值和.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn = 1800+5;
struct Edge
{
int from,to,cap,flow,cost;
Edge(){}
Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
};
struct MCMF
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
void init(int n,int s,int t)
{
this->n=n, this->s=s, this->t=t;
edges.clear();
for(int i=0;i<n;++i) G[i].clear();
}
void AddEdge(int from,int to,int cap,int cost)
{
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BellmanFord(int &flow,int &cost)
{
queue<int> Q;
for(int i=0;i<n;++i) d[i]=INF;
memset(inq,0,sizeof(inq));
d[s]=0,p[s]=0,inq[s]=true,Q.push(s),a[s]=INF;
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for(int i=0;i<G[u].size();++i)
{
Edge &e=edges[G[u][i]];
if(e.cap>e.flow && d[e.to]>d[u]+e.cost)
{
d[e.to]=d[u]+e.cost;
a[e.to]=min(a[u],e.cap-e.flow);
p[e.to]=G[u][i];
if(!inq[e.to]){inq[e.to]=true; Q.push(e.to);}
}
}
}
if(d[t]==INF) return false;
flow +=a[t];
cost +=a[t]*d[t];
int u=t;
while(u!=s)
{
edges[p[u]].flow +=a[t];
edges[p[u]^1].flow -=a[t];
u=edges[p[u]].from;
}
return true;
}
int solve()
{
int flow=0,cost=0;
while(BellmanFord(flow,cost));
return cost;
}
}MM;
int mp[30+5][30+5];
int main()
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&mp[i][j]);
int src=0,dst=n*n-1;
MM.init(2*n*n,src,dst);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
int id=i*n+j;
if(id!=src && id!=dst) MM.AddEdge(id,id+n*n,1,-mp[i][j]);
if(id==src)//因为左上角未拆点,所以它到后继的边与其他边不同
{
MM.AddEdge(id,id+1,1,0);
MM.AddEdge(id,id+n,1,0);
}
else
{
if(j<n-1) MM.AddEdge(id+n*n,id+1,1,0);
if(i<n-1) MM.AddEdge(id+n*n,id+n,1,0);
}
}
printf("%d\n",-MM.solve()+mp[0][0]+mp[n-1][n-1]);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码