Programación Competitiva

#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef int L;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

const L INF = 0x3f3f3f3f;

struct MinCostMaxFlow {
  int N;
  VVL cap, flow, cost;
  VI found;
  VL dist, pi, width;
  VPII dad;

  MinCostMaxFlow(int N) :
    N(N), cap(N, VL(N)), flow(N, VL(N)), cost(N, VL(N)),
    found(N), dist(N), pi(N), width(N), dad(N) {}

  void AddEdge(int from, int to, L cap, L cost) {
    this->cap[from][to] = cap;
    this->cost[from][to] = cost;
  }

  void Relax(int s, int k, L cap, L cost, int dir) {
    L val = dist[s] + pi[s] - pi[k] + cost;
    if (cap && val < dist[k]) {
      dist[k] = val;
      dad[k] = make_pair(s, dir);
      width[k] = min(cap, width[s]);
    }
  }

  L Dijkstra(int s, int t) {
    fill(found.begin(), found.end(), false);
    fill(dist.begin(), dist.end(), INF);
    fill(width.begin(), width.end(), 0);
    dist[s] = 0;
    width[s] = INF;

    while (s != -1) {
      int best = -1;
      found[s] = true;
      for (int k = 0; k < N; k++) {
        if (found[k]) continue;
        Relax(s, k, cap[s][k] - flow[s][k], cost[s][k], 1);
        Relax(s, k, flow[k][s], -cost[k][s], -1);
        if (best == -1 || dist[k] < dist[best]) best = k;
      }
      s = best;
    }

    for (int k = 0; k < N; k++)
      pi[k] = min(pi[k] + dist[k], INF);
    return width[t];
  }

  pair<L, L> GetMaxFlow(int s, int t) {
    L totflow = 0, totcost = 0;
    while (L amt = Dijkstra(s, t)) {
      totflow += amt;
      for (int x = t; x != s; x = dad[x].first) {
        if (dad[x].second == 1) {
          flow[dad[x].first][x] += amt;
          totcost += amt * cost[dad[x].first][x];
        } else {
          flow[x][dad[x].first] -= amt;
          totcost -= amt * cost[x][dad[x].first];
        }
      }
    }
    return make_pair(totflow, totcost);
  }
};

int main(){
    //freopen("C:/Users/Isaac/Documents/QT/Entregar/in.txt","r",stdin);
    int cases; scanf("%d",&cases);
    int P,D,M; scanf("%d%d%d",&P,&D,&M);
    MinCostMaxFlow mcmf(8+cases*cases);
    for(int i=1; i<=cases;i++) mcmf.AddEdge(0,i,1,0);
    for(int i=1; i<=cases;i++){
        for(int j=1; j<=cases;j++)
        {
            int x; scanf("%d",&x);
            mcmf.AddEdge(i,j+i*3,1,-x);
            mcmf.AddEdge(j+i*3,cases*cases+4+j,1,0);
            if(i==1 && j==1) mcmf.AddEdge(cases*cases+4+j,7+cases*cases,P,0);
            else if(i==1 && j==2) mcmf.AddEdge(cases*cases+4+j,7+cases*cases,D,0);
            else  mcmf.AddEdge(cases*cases+4+j,7+cases*cases,M,0);
        }
    }
    pair<int, int> res = mcmf.GetMaxFlow(0,7+cases*cases);
    //printf("%d\n",res.first);
    printf("%d\n",-res.second);
    return 0;
}