poj 3422 Kaka's Matrix Travels （最大费用流（最小费用最大流）+++拆点）

  1   http://poj.org/problem?id=3422 

/*
  2 题意：
  3   ：给一个N*N的方阵，从[1,1]到[n,n]走K次，走过每个方格加上上面的数，
  4   然后这个格上面的数变为0。求可取得的最大的值。
  5   
  6 有是一道网络流题，关键是怎么建图啊。。。。
  7 思路：最小费用最大流。建图很重要，这里用到拆点，将每个点拆成两个，
  8 这两点之间连两条边，一条容量为1，费用为该节点的值，另一条边容量为无穷或k，费用为0，这样保证就算经过这点k次时，费用也只被计算一次。
  9 由于每个点只能往右或者往下走，所以将它和右边及下边的点连一条边，容量为无穷，费用为它的值。源点向第一个点连边，
 10 容量为k，费用为0，最后一个点向汇点连边，容量为k，费用为0。
 11 */
 12 #include<stdio.h>
 13 #define maxn 30000
 14 #include<string.h>
 15 #define inf 0x7fffffff
 16 int n,k;
 17 int que[maxn*10],pre[maxn*10],vis[maxn*10],dis[maxn*10];
 18 int ans;
 19 int max(int x,int y)
 20 {
 21     return x>y?x:y;
 22 }
 23 struct node
 24 {
 25 
 26     int y;
 27     int cost;
 28     int next;
 29     int con;//记录反向边
 30     int cap;
 31 }p[maxn*10];
 32 int next[maxn*10],num;
 33 void add(int x,int y,int ca,int w)
 34 {
 35     p[num].y=y;
 36     p[num].cost=w;
 37     p[num].cap=ca;
 38     p[num].next=next[x];
 39     p[num].con=num+1;//记录反向边
 40     next[x]=num++;
 41 
 42     p[num].y=x;
 43     p[num].cost=-w;//这里要记准
 44     p[num].cap=0;
 45     p[num].next=next[y];
 46     p[num].con=num-1;//记录反向边
 47     next[y]=num++;
 48 
 49 }
 50 int SPFA()
 51 {
 52 
 53     int i;
 54     memset(vis,0,sizeof(vis));
 55     for(i=0;i<=n;i++)
 56     {
 57         dis[i]=-inf;
 58     }
 59     dis[0]=0;
 60     vis[0]=1;
 61     int head=0,tail=0;
 62     que[0]=0;
 63     tail++;
 64     while(head!=tail)
 65     {
 66 
 67         int u=que[head];
 68         vis[u]=0;
 69         for(i=next[u];i!=-1;i=p[i].next)
 70         {
 71                int v=p[i].y;
 72                int cap=p[i].cap;
 73                int cost=p[i].cost;
 74             if(cap&&dis[v]<dis[u]+cost)//求最大费用
 75             {
 76                 dis[v]=dis[u]+cost;
 77                 pre[v]=i;                      //记录边
 78                 if(!vis[v])
 79                 {
 80                     vis[v]=1;
 81                     que[tail++]=v;
 82                     if(tail==maxn)tail=0;
 83                 }
 84 
 85             }
 86         }
 87         head++;
 88         if(head==maxn)head=0;
 89     }
 90     if(dis[n]<=0)return 0;
 91     else return 1;
 92 
 93 }
 94 void end()
 95 {
 96 
 97     int i,u;
 98     for(i=n;i!=0;i=p[p[u].con].y)
 99     {
100         u=pre[i];
101        p[u].cap-=1;
102        p[p[u].con].cap+=1;
103        ans+=p[u].cost;
104     }
105 }
106 int main()
107 {
108     int i,j,w;
109     while(scanf("%d%d",&n,&k)!=EOF)
110     {
111         num=0;
112         memset(next,-1,sizeof(next));
113         for(i=1;i<=n;i++)//建图
114         {
115             for(j=1;j<=n;j++)
116             {
117                 scanf("%d",&w);
118                 int a=(i-1)*n+j;//    拆点
119                 int b=a+n*n;
120                 add(a,b,1,w);//两条变
121                 add(a,b,k,0);
122                 if(i<n)add(b,a+n,k,0);//向下加边
123                 if(j<n)add(b,a+1,k,0);//向右加边
124 
125             }
126 
127         }
128         n=2*n*n+1;
129         add(0,1,k,0);
130         add(n-1,n,k,0);
131 
132 
133 
134         ans=0;
135         while(SPFA())end();
136         printf("%d\n",ans);
137     }
138 }