poj3422Kaka's Matrix Travels

最小费用最大流求的时候把边加为负的输出的时候再负回来就变成求的最大费用了

拆点一个点拆为 i i' i->i'连两条边一条cap为0 cost为给出的值另一条cap为INF cost为0 ，i'到右和下分别设置一条边cap为INF cost为0 设置超级源点到1节点 cap为K cost为0

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<queue>
  7 #define INF 0xfffffff
  8 #define MN 50500
  9 #define MM 100100
 10 using namespace std;
 11 struct node
 12 {
 13     int u,v,cost,cap,next;
 14 }edge[MM];
 15 int head[MN],t,vis[MN],dist[MN],pp[MN];
 16 void init()
 17 {
 18     t  =0;
 19     memset(head,-1,sizeof(head));
 20 }
 21 void add(int u,int v,int c,int p)
 22 {
 23     edge[t].u = u;
 24     edge[t].v = v;
 25     edge[t].cap = c;
 26     edge[t].cost = p;
 27     edge[t].next = head[u];
 28     head[u] = t++;
 29     edge[t].u = v;
 30     edge[t].v = u;
 31     edge[t].cap = 0;
 32     edge[t].cost = -p;
 33     edge[t].next = head[v];
 34     head[v] = t++;
 35 }
 36 int spfa(int s,int en,int n)
 37 {
 38     int u,v,i;
 39     memset(vis,0,sizeof(vis));
 40     memset(pp,-1,sizeof(pp));
 41     for(i = 0 ; i <= n ; i++)
 42     dist[i] =INF;
 43     queue<int>q;
 44     dist[s] = 0;
 45     vis[s] = 1;
 46     q.push(s);
 47     while(!q.empty())
 48     {
 49         u = q.front();
 50         q.pop();
 51         vis[u] = 0;
 52         //cout<<u<<endl;
 53         for(i = head[u] ; i != -1 ; i = edge[i].next)
 54         {
 55             v = edge[i].v;
 56             if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost)
 57             {
 58                 dist[v]  = dist[u]+edge[i].cost;
 59                 pp[v] = i;
 60                 if(!vis[v])
 61                 {
 62                     vis[v] = 1;
 63                     q.push(v);
 64                 }
 65             }
 66         }
 67     }
 68     //cout<<dist[en]<<endl;
 69     if(dist[en]==INF)
 70     return 0;
 71     return 1;
 72 }
 73 int mcmf(int s,int en,int n)
 74 {
 75     int i,mc=0,minf;
 76     while(spfa(s,en,n))
 77     {
 78         minf = INF+1;
 79         for(i = pp[en] ; i!= -1 ; i = pp[edge[i].u])
 80         {
 81             if(minf>edge[i].cap)
 82             minf = edge[i].cap;
 83         }
 84         for(i = pp[en] ; i != -1; i = pp[edge[i].u])
 85         {
 86             edge[i].cap -= minf;
 87             edge[i^1].cap+=minf;
 88         }
 89         //cout<<minf<<" "<<dist[en]<<endl;
 90         mc+=minf*dist[en];
 91     }
 92     return mc;
 93 }
 94 int main()
 95 {
 96     int i,j,k,n,m,a;
 97     while(cin>>n>>k)
 98     {
 99         init();
100         int s = 0,en = 2*n*n+1;
101         add(s,1,k,0);
102         add(2*n*n,en,k,0);
103         for(i = 1; i <= n ; i++)
104             for(j = 1; j <= n ; j++)
105             {
106                 cin>>a;
107                 add((i-1)*n+j,(i-1)*n+j+n*n,1,-a);
108                 add((i-1)*n+j,(i-1)*n+j+n*n,INF,0);
109                 if(i<n)
110                 add((i-1)*n+j+n*n,i*n+j,INF,0);
111                 if(j<n)
112                 add((i-1)*n+j+n*n,(i-1)*n+j+1,INF,0);
113             }
114         cout<<-mcmf(s,en,en)<<endl;
115     }
116     return 0;
117 }