lib/Documentation/docs-sonyckson/2197.cpp

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