题意:
给一个矩阵..每个格子里有数值...每次从左上角走到右下角...每次可以向下走或者向右走...问做了k轮这种操作后能得到的最大值...
题解:
典型的拆点做网络流了...以前做过一些.现在不怎么熟悉了..自己构图还是没搞对..参考了别人的这个图...
http://blog.csdn.net/qq172108805/article/details/7857503
跑最小费用最大流..实际上就是把所有的费用变成其相反数..求最小费用最大流后再反回来就是....
总结:
此类拆点问题普遍是把一个点拆成"入点"和"出点"...在根据关系做边...在每个点对之间(同一个点的入点和出点)可以根据题目要求加很多限制...
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<time.h> #include<map> #include<algorithm> #define ll long long #define eps 1e-5 #define oo 1000000007 #define pi acos(-1.0) #define MAXN 5050 #define MAXM 500005 using namespace std; struct MCMF { struct node { int x,y,c,v,next; }line[MAXM]; int Lnum,_next[MAXN],pre[MAXN],dis[MAXN],flow,cost; bool inqueue[MAXN]; void initial(int n) { Lnum=-1; for (int i=0;i<=n;i++) _next[i]=-1; } void addline(int x,int y,int c,int v) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c,line[Lnum].v=v; line[++Lnum].next=_next[y],_next[y]=Lnum; line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0,line[Lnum].v=-v; } bool SPFA(int s,int e) { int x,k,y; queue<int> Q; while (!Q.empty()) Q.pop(); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); Q.push(s); dis[s]=0,pre[s]=-1; while (!Q.empty()) { x=Q.front(),Q.pop(),inqueue[x]=false; for (k=_next[x];k!=-1;k=line[k].next) if (line[k].c) { y=line[k].y; if (dis[y]>dis[x]+line[k].v) { dis[y]=dis[x]+line[k].v; pre[y]=k; if (!inqueue[y]) { inqueue[y]=true; Q.push(y); } } } } if (dis[e]>oo) return false; flow=oo,cost=0; for (k=pre[e];k!=-1;k=pre[line[k].x]) flow=min(flow,line[k].c),cost+=line[k].v; cost*=flow; for (k=pre[e];k!=-1;k=pre[line[k].x]) line[k].c-=flow,line[k^1].c+=flow; return true; } int MinCostMaxFlow(int s,int e) { int Aflow=0,Acost=0; while (SPFA(s,e)) { Aflow+=flow; Acost+=cost; } return Acost; } }T; int main() { int R,C,k,i,j,x,t1,t2,s,e; while (~scanf("%d%d",&R,&k) && R) { C=R,s=R*C*2+1,e=s+1,T.initial(e); for (i=0;i<R;i++) for (j=0;j<C;j++) { scanf("%d",&x),x=-x,t1=(i*C+j)<<1; T.addline(t1,t1|1,1,x),T.addline(t1,t1|1,k-1,0); if (i!=R-1) { t2=((i+1)*C+j)<<1; T.addline(t1|1,t2,k,0); } if (j!=C-1) { t2=(i*C+j+1)<<1; T.addline(t1|1,t2,k,0); } } T.addline(s,0,k,0),T.addline((R*C<<1)-1,e,k,0); printf("%d\n",-T.MinCostMaxFlow(s,e)); } return 0; }