题目描述 Description

　　给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

　　输入描述 Input Description

　　第一行两个数n,k(1<=n<=50, 0<=k<=10)

　　接下来n行,每行n个数,分别表示矩阵的每个格子的数

　　输出描述 Output Description

　　一个数，为最大值

　　样例输入 Sample Input

　　3 1

　　1 2 3

　　0 2 1

　　1 4 2

　　样例输出 Sample Output

　　11

　　数据范围及提示 Data Size & Hint

　　1<=n<=50, 0<=k<=10

　　这是我学了网络流之后自己写的第一道建模题，虽说这道题也是一道很普通的题。

　　建图如下:很显然想到把每个点当成点，向下面的点和右边的点连边，至于权值的事情，那就把一个点拆成两个点，分为上点和下点，上点向下点连一条费用为该点点权，容量为1的边(因为每个数只能取一次)，但发现取完这个数后这个点还是可以走的，那就让上点再连一条费用为0，容量为正无穷的边(表示可以走很多次)到下点。汇点显然是最后一个点的下点，至于源点的设定，因为题目中有走k次的要求，那就新创一个点，连向起点的上点，费用为0，容量为K,因为每一次取容量为1，所以取K次的意思就相当于走k条增广路。然后就求一遍最大费用流即可。建图还有一个比较烦的就是每个点编号的编排，具体编排方法下文注释上有。

　　1 #include

　　2 #include

　　3 #include

　　4 #include

　　5 #include

　　6 #include

　　7 using namespace std;

　　8 typedef long long LL;

　　9 inline int read()

　　10 {

　　11 int x=0,f=1;char c=getchar();

　　12 while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}

　　13 while(isdigit(c)){x=x*10+c-'0';c=getchar();}

　　14 return x*f;

　　15 }

　　16 const int oo=2147000000;

　　17 const int maxn=100000;

　　18 struct Edge

　　19 {

　　20 int u,v,f,w,next;

　　21 Edge() {}

　　22 Edge(int _1,int _2,int _3,int _4,int _5) : u(_1),v(_2),f(_3),w(_4),next(_5) {}

　　23 }e[maxn];

　　24 int n,k,first[maxn],vis[maxn],dis[maxn],a[100][100],cnt,s,t,ans;

　　25 queue Q;

　　26 void add(int i,int a,int b,int c,int d)

　　27 {

　　28 e[i]=Edge(a,b,c,d,first[a]);

　　29 first[a]=i;

　　30 }

　　31 void addEdge(int i,int a,int b,int c,int d){add(2*i,a,b,c,d);add(2*i+1,b,a,0,-d);}

　　32 bool spfa()

　　33 {

　　34 memset(vis,0,sizeof(vis));

　　35 for(int i=0;i<=2*n*n;i++)dis[i]=-oo;

　　36 while(Q.size())Q.pop();

　　37 dis[t]=0;vis[t]=1;Q.push(t);

　　38 while(Q.size())

　　39 { 　 大连妇科医院哪个好  http://www.83692222.cn/

　   40 int now=Q.front();Q.pop();

　　41 for(int i=first[now];i!=-1;i=e[i].next)

　　42 if(dis[now]+e[i^1].w>dis[e[i].v] && e[i^1].f)

　　43 {

　　44 dis[e[i].v]=dis[now]+e[i^1].w;

　　45 if(!vis[e[i].v])

　　46 {

　　47 vis[e[i].v]=1;

　　48 Q.push(e[i].v);

　　49 }

　　50 }

　　51 vis[now]=0;

　　52 }

　　53 return dis[s]!=-oo;

　　54 }

　　55 int dfs(int x,int flow)

　　56 {

　　57 vis[x]=1;

　　58 if(x==t)return flow;

　　59 int now,used=0;

　　60 for(int i=first[x];i!=-1;i=e[i].next)

　　61 if(dis[e[i].v]==dis[x]-e[i].w && e[i].f && !vis[e[i].v])

　　62 {

　　63 now=flow-used;

　　64 now=dfs(e[i].v,min(now,e[i].f));

　　65 ans+=now*e[i].w;

　　66 e[i].f-=now;e[i^1].f+=now;

　　67 used+=now;

　　68 if(used==flow)return flow;

　　69 }

　　70 return used;

　　71 }

　　72 void zkw()

　　73 {

　　74 while(spfa())

　　75 {

　　76 vis[t]=1;

　　77 while(vis[t])

　　78 {

　　79 memset(vis,0,sizeof(vis));

　　80 dfs(s,oo);

　　81 }

　　82 }

　　83 }

　　84 int main()

　　85 {

　　86 memset(first,-1,sizeof(first));

　　87 n=read();k=read();

　　88 for(int i=0;i

　　89 for(int i=0;i

　　90 for(int j=0;j

　　91 {

　　92 addEdge(cnt,2*(i*n+j),2*(i*n+j)+1,1,a[i][j]);cnt++;

　　93 addEdge(cnt,2*(i*n+j),2*(i*n+j)+1,oo,0);cnt++;

　　94 if(j!=n-1)addEdge(cnt,2*(i*n+j)+1,2*(i*n+j+1),oo,0);cnt++;//向右边

　　95 if(i!=n-1)addEdge(cnt,2*(i*n+j)+1,2*((i+1)*n+j),oo,0);cnt++;//下面

　　96 }

　　97 addEdge(cnt,2*n*n,0,k,0);cnt++;

　　98 s=2*n*n;t=2*n*n-1;

　　99 zkw();

　　100 printf("%d",ans);

　　101 return 0;

　　102 }

　　103 /*

　　104 建图：

　　105 原图中a[i][j]，对应编号为i*n+j，拆成两个点，一个是2*(i*n+j)，另一个是2*(i*n+j)+1

　　106 (i,j)上点向下点连两条边，下点向下面和右面连一条边

　　107 源点 2*n*n 向0,0连一条边

　　108 汇点 2*n*n-1

　　109 */