Documentation/docs-sonyckson/2197.cpp

   1 // another fine solution by misof
   2 // #includes {{{
   3 #include <algorithm>
   4 #include <numeric>
   5
   6 #include <iostream>
   7 #include <sstream>
   8 #include <string>
   9 #include <vector>
  10 #include <queue>
  11 #include <set>
  12 #include <map>
  13
  14 #include <cstdio>
  15 #include <cstdlib>
  16 #include <cctype>
  17 #include <cassert>
  18
  19 #include <cmath>
  20 #include <complex>
  21 using namespace std;
  22 // }}}
  23
  24 /////////////////// PRE-WRITTEN CODE FOLLOWS, LOOK DOWN FOR THE SOLUTION ////////////////////////////////
  25
  26 // pre-written code {{{
  27 #define CLEAR(t) memset((t),0,sizeof(t))
  28 #define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
  29 typedef pair<int,int> PII;
  30 #define REP(i,n) for(int i=0;i<(int)(n);++i)
  31 #define SIZE(t) ((int)((t).size()))
  32 // }}}
  33
  34 /////////////////// CODE WRITTEN DURING THE COMPETITION FOLLOWS ////////////////////////////////
  35 #define MX 200
  36 int CAP[MX][MX];
  37 int COST[MX][MX];
  38 int flow[MX][MX];
  39
  40 PII MC_MAXFLOW(int N, int source, int sink) {
  41   int flowSize = 0;
  42   int flowCost = 0;
  43   int infinity = 1; while (2*infinity > infinity) infinity *= 2;
  44
  45   // speed optimization #1: adjacency graph
  46   // speed optimization #2: cache the degrees
  47   vector<int> deg(N,0);
  48   vector<vector<int> > G(N);
  49   for (int i=0; i<N; i++) for (int j=0; j<i; j++) if (CAP[i][j]>0 || CAP[j][i]>0) {
  50     deg[i]++;
  51     deg[j]++;
  52     G[i].push_back(j); G[j].push_back(i);
  53   }
  54
  55   vector<int> potential(N,0);
  56
  57   while (1) {
  58     // use dijkstra to find an augmenting path
  59     vector<int> from(N,-1);
  60     vector<int> dist(N,infinity);
  61
  62     priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
  63     Q.push(make_pair(0,source));
  64     from[source]=-2; dist[source] = 0;
  65
  66     while (!Q.empty()) {
  67       int howFar = Q.top().first;
  68       int where = Q.top().second;
  69       Q.pop();
  70
  71       if (dist[where] < howFar) continue;
  72
  73       for (int i=0; i<deg[where]; i++) {
  74         int dest = G[where][i];
  75
  76         // now there are two possibilities: add flow in the right direction, or remove in the other one
  77         if (flow[dest][where] > 0)
  78           if (dist[dest] > dist[where] + potential[where] - potential[dest] - COST[dest][where]) {
  79             dist[dest] = dist[where] + potential[where] - potential[dest] - COST[dest][where];
  80             from[dest] = where;
  81             Q.push(make_pair(dist[dest],dest));
  82           }
  83
  84         if (flow[where][dest] < CAP[where][dest])
  85           if (dist[dest] > dist[where] + potential[where] - potential[dest] + COST[where][dest]) {
  86             dist[dest] = dist[where] + potential[where] - potential[dest] + COST[where][dest];
  87             from[dest] = where;
  88             Q.push(make_pair(dist[dest],dest));
  89           }
  90
  91         // no breaking here, we need the whole graph
  92       }
  93     }
  94
  95     // update vertex potentials
  96     for (int i=0; i<N; i++) potential[i] += dist[i];
  97
  98     // if there is no path, we are done
  99     if (from[sink] == -1) return make_pair(flowSize,flowCost);
 100
 101     // construct an augmenting path
 102     int canPush = infinity;
 103     int where = sink;
 104
 105     while (1) {
 106       int prev=from[where];
 107       if (prev==-2) break;
 108       if (flow[where][prev])
 109         canPush = min( canPush, flow[where][prev] );
 110       else
 111         canPush = min( canPush, CAP[prev][where] - flow[prev][where] );
 112       where=prev;
 113     }
 114
 115     // update along the path
 116     where = sink;
 117
 118     while (1) {
 119       int prev=from[where];
 120       if (prev==-2) break;
 121       if (flow[where][prev]) {
 122         flow[where][prev] -= canPush;
 123         flowCost -= canPush * COST[where][prev];
 124       } else {
 125         flow[prev][where] += canPush;
 126         flowCost += canPush * COST[prev][where];
 127       }
 128       where=prev;
 129     }
 130     flowSize += canPush;
 131   }
 132   return make_pair(-1,47);
 133 }
 134 int main(){
 135         int N, M, K;
 136         int k;
 137         int casos = 0;
 138         scanf("%i", &casos);
 139         for(int h  = 0; h< casos;h++){
 140                 scanf("%i %i %i", &N, &M, &K);
 141                 CLEAR(CAP), CLEAR(COST), CLEAR(flow);
 142                 FOR(i, 1, N)  CAP[0][i] = K;
 143                 FOR(j, N+1, 2*N) CAP[j][2*N+1] = K;
 144                 FOR(i, 1, N)FOR(j, N+1, 2*N) CAP[i][j] = 1;
 145
 146
 147 //              printf("%i %i %i\n", N, M, K);
 148                 FOR(i, 1, N)FOR(j, N+1, 2*N) COST[i][j] = 50000;
 149
 150                 for(int i=0;i<M;i++){
 151                         int f, t, d;
 152                         scanf("%i %i %i", &f, &t, &d);
 153                         f++, t++;
 154                         COST[f][t+N] = d ;
 155                 }
 156                 pair<int, int> p = MC_MAXFLOW(2*N+2, 0, 2*N+1);
 157                 if( p.first != K*N || p.second >= 50000) printf("-1\n");
 158                 else printf("%i\n", p.second);
 159 //              printf("              %i %i\n", p.first, p.second);
 160         }
 161         return 0;
 162 }