POJ 3422 Kaka's Matrix Travels(费用流)
http://poj.org/problem?id=3422
题意:
给一个N*N的方阵,从[1,1]到[n,n]走K次,走过每个方格加上上面的数(每个方格初始都有一个非负数),然后这个格上面的数变为0。求可取得的最大的值。
分析:
其实把每个网格看成一条边的话,那么我们就是等于要找K次最小费用增广路径即可(就是一个求最小费用最大流的过程). 建图如下:
源点s编号0,n*n个网格每个网格分成两个点i和i+n*n, 汇点t编号为n*n*2+1.
从源点s到1号节点有边(s , 1, K)
从每个网格到自己有边(i, i+n*n, 1, -cost) 和(i, i+n*n, INF, 0) (注意这里的-cost,因为原题要我们求最大值)
从每个网格i到它的右或下那个网格j有边(i+n*n, j, INF, 0)
从最右下角到汇点t有边(2*n*n, t, INF, 0)
最终我们求得的最小费用的绝对值就是权值最大值.
AC代码:
最小费用取绝对值解法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn= 51*51*2+10;
struct Edge
{
int from,to,cap,flow,cost;
Edge(){}
Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int a[maxn];
int p[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)
{
memset(inq,0,sizeof(inq));
for(int i=0;i<n;++i) d[i]=INF;
queue<int> Q;
d[s]=0,inq[s]=true, Q.push(s),a[s]=INF,p[s]=0;
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[55][55];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)==2)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&mp[i][j]);
int src=0,dst=n*n*2+1;
MM.init(n*n*2+2,src,dst);
MM.AddEdge(src,1,k,0);
MM.AddEdge(n*n*2,dst,INF,0);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
int id=(i-1)*n+j;
MM.AddEdge(id,id+n*n,1,-mp[i][j]);
MM.AddEdge(id,id+n*n,INF,0);
if(j+1<=n) MM.AddEdge(id+n*n,id+1,INF,0);
//这里如果写if(id+1<=n*n)是错的,最后一列虽然能+1,但是无后继
if(i+1<=n) MM.AddEdge(id+n*n,id+n,INF,0);
}
printf("%d\n",-MM.solve());
}
return 0;
}
AC代码:
直接求最大费用路径解法,两个程序的不同点在下面已经标出来了,注意细节
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn= 51*51*2+10;
struct Edge
{
int from,to,cap,flow,cost;
Edge(){}
Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
int d[maxn];
int a[maxn];
int p[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)
{
memset(inq,0,sizeof(inq));
for(int i=0;i<n;++i) d[i]=-1; //修改1
queue<int> Q;
d[s]=0,inq[s]=true, Q.push(s),a[s]=INF,p[s]=0;
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)//修改2
{
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]==-1) return false;//修改3
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[55][55];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)==2)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&mp[i][j]);
int src=0,dst=n*n*2+1;
MM.init(n*n*2+2,src,dst);
MM.AddEdge(src,1,k,0);
MM.AddEdge(n*n*2,dst,INF,0);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
int id=(i-1)*n+j;
MM.AddEdge(id,id+n*n,1,mp[i][j]);//修改4
MM.AddEdge(id,id+n*n,INF,0);
if(j+1<=n) MM.AddEdge(id+n*n,id+1,INF,0);
//这里如果写if(id+1<=n*n)是错的,最后一列虽然能+1,但是无后继
if(i+1<=n) MM.AddEdge(id+n*n,id+n,INF,0);
}
printf("%d\n",MM.solve());//修改5
}
return 0;
}
分享到:
相关推荐
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
poj2516代码最小费用最大流
POJ北大在线测评系统离线题库,里面包含1002-3422题,可以离线刷题。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj-2528 Mayor's posters 测试数据及答案
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)