daily pastebin goal
71%
SHARE
TWEET

Untitled

a guest Oct 15th, 2017 227 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 128;
  6. const int INF = (1e9) + 7;
  7.  
  8. struct edge {
  9.     int to,reversed,flow,capacity,cost;
  10.     edge(){}
  11.     edge(int a, int b, int c, int d) {
  12.         to=a;
  13.         reversed=b;
  14.         flow=0;
  15.         capacity=c;
  16.         cost=d;
  17.     }
  18. };
  19.  
  20. struct el {
  21.     int vertex,cost;
  22.     el(){}
  23.     el(int a, int b) {
  24.         vertex=a;
  25.         cost=b;
  26.     }
  27.     bool operator <(const el &a) const {
  28.         return cost>a.cost;
  29.     }
  30. };
  31.  
  32. int tests,current_case;
  33. int n,a[N][N];
  34. int nodes,s,t;
  35. vector < edge > v[N];
  36. priority_queue < el > q;
  37. int dist[N],from[N];
  38. int current_flow[N];
  39. int link[N];
  40. int pot[N];
  41.  
  42. void initialize_data() {
  43.     int i;
  44.     for(i=0;i<N;i++) v[i].clear();
  45. }
  46.  
  47. void message(int current_case) {
  48.     fprintf(stderr, "Case %d solved!\n", current_case);
  49. }
  50.  
  51. void add_edge(int a, int b, int c, int d) {
  52.     edge x=edge(b,v[b].size(),c,d);
  53.     edge y=edge(a,v[a].size(),0,-d);
  54.     v[a].push_back(x);
  55.     v[b].push_back(y);
  56. }
  57.  
  58. void bellman_ford() {
  59.     int i,j,z;
  60.     for(i=1;i<=nodes;i++) pot[i]=INF;
  61.     pot[s]=0;
  62.     for(i=1;i<nodes;i++) {
  63.         for(j=1;j<=nodes;j++) {
  64.             for(z=0;z<(int)(v[j].size());z++) {
  65.                 dist[v[j][z].to]=min(dist[v[j][z].to],dist[j]+v[j][z].cost);
  66.             }
  67.         }
  68.     }
  69. }
  70.  
  71. pair < int, int > mincost_maxflow(int flow) {
  72.     int i,current_distance,to,w;
  73.     el curr;
  74.     int max_flow=0,min_cost=0,transmitted,where,prev;
  75.    
  76.     bellman_ford();
  77.     while(max_flow<flow) {
  78.         for(i=1;i<=nodes;i++) dist[i]=INF,current_flow[i]=0,from[i]=-1;
  79.         dist[s]=0;
  80.         current_flow[s]=INF;
  81.         q.push(el(s,0));
  82.         while(!q.empty()) {
  83.             curr=q.top();
  84.             q.pop();
  85.             for(i=0;i<(int)(v[curr.vertex].size());i++) if(v[curr.vertex][i].flow<v[curr.vertex][i].capacity) {
  86.                 to=v[curr.vertex][i].to;
  87.                 w=v[curr.vertex][i].cost;
  88.                 current_distance=curr.cost+w+pot[curr.vertex]-pot[to];
  89.                 if(current_distance<dist[to]) {
  90.                     dist[to]=current_distance;
  91.                     current_flow[to]=min(current_flow[curr.vertex],v[curr.vertex][i].capacity-v[curr.vertex][i].flow);
  92.                     link[to]=i;
  93.                     from[to]=curr.vertex;
  94.                     q.push(el(to,current_distance));
  95.                 }
  96.             }
  97.         }
  98.         if(current_flow[t]==0) break;
  99.         transmitted=min(current_flow[t],flow-max_flow);
  100.         max_flow+=transmitted;
  101.         where=t;
  102.         while((prev=from[where])!=(-1)) {
  103.             v[prev][link[where]].flow+=transmitted;
  104.             v[where][v[prev][link[where]].reversed].flow-=transmitted;
  105.             min_cost+=transmitted*v[prev][link[where]].cost;
  106.             where=prev;
  107.         }
  108.     }
  109.     return make_pair(max_flow,min_cost);
  110. }
  111.  
  112. int main() {
  113.     pair < int, int > ans;
  114.     int i,j;
  115.    
  116.     scanf("%d", &tests);
  117.     for(current_case=1;current_case<=tests;current_case++) {
  118.         initialize_data();
  119.         scanf("%d", &n);
  120.         for(i=1;i<=n;i++) {
  121.             for(j=1;j<=n;j++) {
  122.                 scanf("%d", &a[i][j]);
  123.             }
  124.         }
  125.         nodes=n+n+2;
  126.         s=nodes-1;
  127.         t=nodes;
  128.         for(i=1;i<=n;i++) add_edge(s,i,1,0);
  129.         for(i=1;i<=n;i++) {
  130.             for(j=1;j<=n;j++) {
  131.                 add_edge(i,n+j,1,-a[i][j]);
  132.             }
  133.         }
  134.         for(i=1;i<=n;i++) add_edge(n+i,t,1,0);
  135.         ans=mincost_maxflow(n);
  136.         printf("Case %d: %d\n", current_case, -ans.second);
  137.         message(current_case);
  138.     }
  139.  
  140.     return 0;
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top