JumpTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1275 Accepted Submission(s): 547 Problem Description There are n*m grids, each grid contains a number, ranging from 0-9. Your initial energy is zero. You can play up to K times the game, every time you can choose any one of the grid as a starting point (but not traveled before) then you can choose a grid on the right or below the current grid to jump, but it has not traveled before. Every time you can jump as many times as you want, as long as you do not violate rules. If you are from (x1, y1) to (x2, y2), then you consume |x1-x2|+|y1-y2|-1 energies. Energy can be negative. However, in a jump, if you start position and end position has same numbers S, then you can increase the energy value by S. Give me the maximum energy you can get. Notice that you have to go each grid exactly once and you don’t have to play exactly K times. Input The first line is an integer T, stands for the number of the text cases. Then T cases followed and each case begin with three numbers N, M and K. Means there are N rows and M columns, you have K times to play. Then N lines follow, each line is a string which is made up by M numbers. The grids only contain numbers from 0 to 9. (T<=100, N<=10，M<=10，K<=100) Output Each case, The first you should output “Case x : ”,(x starting at 1),then output The maximum number of energy value you can get. If you can’t reach every grid in no more than K times, just output -1. Sample Input 5 1 5 1 91929 1 5 2 91929 1 5 3 91929 3 3 3 333 333 333 3 3 2 333 333 333 Sample Output Case 1 : 0 Case 2 : 15 Case 3 : 16 Case 4 : 18 Case 5 : -1 Author FZU Source Recommend |
我这是有多久没好好刷题了啊……
说题意，给出n*m的数据，选择k条不重复的道路，起点终点任意，但是需要保证每个点都要走到，每步只能选择右边或者下边的点（即，只能竖着往下走或者横着往右走，不可以斜着往右下走）每步的费用是+(ii-i+jj-j-1)-（num[i][j]==num[ii][jj]?num[i][j]:0）
很容易想到用网络流控制流量，用费用流控制费用（好像说的是废话==），既然要要求每个点都走，有了流量控制，就一定要拆点。那么就拆成了x部,y部。很容易想到从s到x每个点cap=1 cost=0,y到t每个点cap=1 cost=0,x到可行的y cap=1 cost=题目已知的值（注意是相反数）然而k要如何限制？再加一个S'，S->S' cap=k cost=0,S'到Y的每个点cap=1 cost=0。
为什么这么建边就可以保证了呢？这样可以保证不会先选S'->Y
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=0x3f3f3f3f;//无穷大
const int maxm=11111;//边的最大数量，为原图的两倍
const int maxn=222;//点的最大数量
int node,src,dest,edge;//node节点数，src源点，dest汇点，edge边数
int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head链表头，p记录可行流上节点对应的反向边，dis计算距离
int n,m,k;
struct edgenode
{
int to;//边的指向
int flow;//边的容量
int cost;//边的费用
int next;//链表的下一条边
} edges[maxm];
void prepare(int _node,int _src,int _dest);
void addedge(int u,int v,int f,int c);
bool spfa();
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node;
src=_src;
dest=_dest;
for (int i=0; i<node; i++)
{
head[i]=-1;
vis[i]=false;
}
edge=0;
}
void addedge(int u,int v,int f,int c)
{
edges[edge].flow=f;
edges[edge].cost=c;
edges[edge].to=v;
edges[edge].next=head[u];
head[u]=edge++;
edges[edge].flow=0;
edges[edge].cost=-c;
edges[edge].to=u;
edges[edge].next=head[v];
head[v]=edge++;
}
bool spfa()
{
int i,u,v,l,r=0,tmp;
for (i=0; i<node; i++) dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for (l=0; l!=r; ((++l>=maxn)?l=0:1))
{
for (i=head[u=q[l]],vis[u]=false; i!=-1; i=edges[i].next)
{
if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost))
{
dis[v]=tmp;
p[v]=i^1;
if (vis[v]) continue;
vis[q[r++]=v]=true;
if (r>=maxn) r=0;
}
}
}
return p[dest]>=0;
}
int spfaflow()
{
int i,ret=0,delta,sum=0;
while (spfa())
{
//按记录原路返回求流量
for (i=p[dest],delta=oo; i>=0; i=p[edges[i].to])
{
delta=min(delta,edges[i^1].flow);
}
for (int i=p[dest]; i>=0; i=p[edges[i].to])
{
edges[i].flow+=delta;
edges[i^1].flow-=delta;
}
sum+=delta;//流量
ret+=delta*dis[dest];
}
// printf("sum=%d ",sum);
// printf("n=%d,m=%d\n",n,m);
if(sum!=n*m)return 1;
return ret;
}
int num[20][20],b[20][20];
int main()
{
// freopen("cin.txt","r",stdin);
int t,cas=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
// printf("n=%d,m=%d\n",n,m);
for(int i=0;i<n;i++)
{
char tmp[20];
scanf("%s",tmp);
for(int j=0;j<m;j++)
num[i][j]=tmp[j]-'0';
}
//for(int i=0;i<n;i++)for(int j=0;j<m;j++)printf("%d ",num[i][j]);
prepare(2*n*m+3,2*n*m,2*n*m+2);
addedge(2*m*n,2*m*n+1,k,0);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int u=j+i*m;
addedge(2*n*m,u,1,0);
addedge(u+n*m,n*m*2+2,1,0);
addedge(2*m*n+1,u+n*m,1,0);
for(int ii=i+1;ii<n;ii++)
{
for(int jj=j;jj<=j;jj++)
{
if(i==ii&&j==jj)continue;
int uu=jj+ii*m+n*m;
int tmp=num[i][j]==num[ii][jj]?num[i][j]:0;
addedge(u,uu,1,+(ii-i+jj-j-1)-tmp);
}
}
for(int ii=i;ii<=i;ii++)
{
for(int jj=j+1;jj<m;jj++)
{
if(i==ii&&j==jj)continue;
int uu=jj+ii*m+n*m;
int tmp=num[i][j]==num[ii][jj]?num[i][j]:0;
addedge(u,uu,1,+(ii-i+jj-j-1)-tmp);
}
}
}
}
printf("Case %d : %d\n",cas++,-spfaflow());
}
return 0;
}
京公网安备 11010502036488号