POJ 2516 最小费用最大流

   1:  /**

   2:  因为e ==0 所以 pe[v]   pe[v]^1 是两条相对应的边

   3:  E[pe[v]].c -= aug;            E[pe[v]^1].c += aug;

   4:  

   5:  */

   6:  #include <queue>

   7:  #include <iostream>

   8:  #include <string.h>

   9:  #include <stdio.h>

  10:  #include <map>

  11:  using namespace std;

  12:  #define V 30010      // vertex

  13:  #define E 150010      // edge

  14:  #define INF 0x3F3F3F3F

  15:  struct MinCostMaxFlow

  16:  {

  17:      struct Edge

  18:      {

  19:          int v, next, cap, cost;  // cap 为容量, cost为单位流量费用

  20:      } edge[E];

  21:   

  22:      int head[V], pe[V], pv[V];            // 每个节点的第一条edge[idx]的编号.

  23:      int  dis[V];            // the shortest path to the src

  24:      bool vis[V];            // visted

  25:      // pe[v]  存放在增广路上到达v的边(u,v) 在edge[]的位置

  26:      // pv[u]  存放在增广路上从u出发的边(u,v) 在edge[]中的位置

  27:      int e, src, sink;            // the index of the edge

  28:      int VertexNum;               // N the num of the vertex. M the num of edges

  29:      void addedge(int  u, int v, int cap, int cost)

  30:      {

  31:          edge[e].v = v, edge[e].cap = cap;

  32:          edge[e].cost = cost,edge[e].next = head[u], head[u] = e++;

  33:          edge[e].v = u, edge[e].cap = 0;

  34:          edge[e].cost = -1*cost, edge[e].next = head[v], head[v] = e++;

  35:      }

  36:      // 求最短路,不存在负环的时候,比 DFS快

  37:      int SPFABFS()

  38:      {

  39:          memset(vis, 0 ,sizeof(vis));

  40:          memset(pv, -1, sizeof(pv));

  41:          for(int i=0; i<V; i++) dis[i] = INF;

  42:          queue<int> Q;

  43:          Q.push(src);

  44:          vis[src] = 1, dis[src] = 0;

  45:          while(!Q.empty())

  46:          {

  47:              int u = Q.front();

  48:              Q.pop();

  49:              vis[u] = 0;

  50:              for(int i=head[u]; i!=-1; i=edge[i].next)

  51:              {

  52:                  int v = edge[i].v;

  53:                  if(edge[i].cap > 0 &&  dis[v] > dis[u] + edge[i].cost  )

  54:                  {

  55:                      dis[v] = dis[u] + edge[i].cost;

  56:                      if(!vis[v])

  57:                      {

  58:                          Q.push(v);

  59:                          vis[v] = 1;

  60:                      }

  61:                      pv[v] = u;

  62:                      pe[v] = i;

  63:                  }

  64:              }

  65:          }

  66:          if(dis[sink] == INF) return -2;          // can‘t from src to sink.

  67:          return dis[sink];

  68:      }

  69:   

  70:      pair<int,int> MCMF()

  71:      {

  72:          int maxflow = 0, mincost = 0;

  73:          while(SPFABFS())

  74:          {

  75:              if(pv[sink] == -1) break;

  76:              int aug = INF;

  77:              for(int i= sink; i!= src; i = pv[i])

  78:                  aug =min(aug, edge[pe[i]].cap);

  79:              maxflow += aug;

  80:              mincost += aug * dis[sink];

  81:              for(int i = sink; i!= src; i = pv[i])

  82:              {

  83:                  edge[pe[i]].cap -= aug;

  84:                  edge[pe[i]^1].cap += aug;

  85:              }

  86:          }

  87:          return make_pair(maxflow, mincost);

  88:      }

  89:      int solve()

  90:      {

  91:          int N,M,K;

  92:          while(scanf("%d%d%d", &N , &M, &K) && N!=0 && M!=0 && K!=0)

  93:          {

  94:              int tmp;

  95:              vector<int> need[55];

  96:              for(int i=0; i<N; i++)

  97:              {

  98:                  for(int j=0; j<K; j++)

  99:                  {

 100:                      scanf("%d", &tmp);

 101:                      need[i].push_back(tmp);

 102:                  }

 103:              }

 104:              vector<int> supply[55];

 105:              for(int i =0; i<M; i++)

 106:              {

 107:                  for(int j=0; j<K; j++)

 108:                  {

 109:                      scanf("%d", &tmp);

 110:                      supply[i].push_back(tmp);

 111:                  }

 112:              }

 113:              vector<vector<vector<int> > > cost;

 114:              for(int i=0; i<K; i++)

 115:              {

 116:                  vector<vector<int> > y;

 117:                  for(int j=0; j<N; j++)

 118:                  {

 119:                      vector<int> x;

 120:                      for(int k = 0; k<M; k++)

 121:                      {

 122:                          scanf("%d", &tmp);

 123:                          x.push_back(tmp);

 124:                      }

 125:                      y.push_back(x);

 126:                  }

 127:                  cost.push_back(y);

 128:              }

 129:              int ret = 0;

 130:              bool flag = true;

 131:              for(int k = 0; k < K; k++)

 132:              {

 133:                  e=0;

 134:                  memset(head, -1,sizeof(head));

 135:                  // M suppliers

 136:                  src = 0;

 137:                  sink = M+N+1;

 138:                  VertexNum = M+N+2;

 139:                  for(int i=0; i<M; i++)

 140:                  {

 141:                      addedge(src,i+1,supply[i][k],0);

 142:                  }

 143:                  int x = 0;

 144:                  for(int i=0; i<N; i++)

 145:                  {

 146:                      x+= need[i][k];

 147:                      addedge(M+i+1,sink, need[i][k], 0);

 148:                  }

 149:                  for(int j=0; j<M; j++)

 150:                  {

 151:                      for(int i=0; i<N; i++)

 152:                      {

 153:                          addedge(j+1, M+i+1,INF,cost[k][i][j]);

 154:                      }

 155:                  }

 156:                  pair<int,int> res = MCMF();

 157:                  if(res.first < x)

 158:                  {

 159:                      flag = 0;

 160:                      break;

 161:                  }

 162:                  ret += res.second;

 163:              }

 164:              if(flag) cout<<ret<<endl;

 165:              else cout<<-1<<endl;

 166:          }

 167:      }

 168:  } mcmf;

 169:   

 170:   

 171:  int main()

 172:  {

 173:      freopen("1.txt","r",stdin);

 174:      mcmf.solve();

 175:      return 0;

 176:  }