daily pastebin goal
36%
SHARE
TWEET

Untitled

a guest Jul 20th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <memory>
  3. #include <deque>
  4. #include <limits>
  5. #include <fstream>
  6. #include <vector>
  7.  
  8.  
  9. using namespace std;
  10. const int MAX = 500;
  11. const int AAA=1000000000;
  12. int source,dest,n;
  13. int z=0;
  14. int counter=0;
  15. int Cmax=0;
  16. vector< vector<int> > W( MAX );
  17. deque<int> q;
  18. int answer[MAX];
  19. int m[MAX][MAX];
  20. int used[MAX],p[MAX];
  21. int color[MAX];
  22.  
  23. int min(int i, int j)
  24. {
  25.   return (i < j) ? i : j;
  26. }
  27.  
  28.  
  29. void bfs(int v)
  30. {
  31.   int First;
  32.   q.push_front(v);
  33.   while(!q.empty())
  34.   {
  35.      First = q[0];
  36.      if (First == dest) return;
  37.      q.pop_front();
  38.      used[First] = 1;
  39.        int s=W[First].size();
  40.  
  41.      for(int ii=0;ii<s;ii++)
  42.      {
  43.          int i=W[First][ii];
  44.          if ((((m[First][i])&z) > 0) && (!used[i]))
  45.          {
  46.              p[i] = First;
  47.              q.push_back(i);
  48.          }
  49.      }
  50.   }
  51. }
  52.  
  53.  
  54.  
  55. void Rebuild(int k, int flow)
  56. {
  57.   if (p[k] == -1) return;
  58.   Rebuild(p[k],flow);
  59.   m[p[k]][k] -= flow;
  60.   m[k][p[k]] += flow;
  61. }
  62.  
  63.  
  64.  
  65.  
  66.  
  67. int FindFlow(int k)
  68. {
  69.   int x;
  70.   if (p[k] == -1) return INT_MAX;
  71.   x = FindFlow(p[k]);
  72.   return min(x,m[p[k]][k]);
  73. }
  74. void DFSVISIT(int a) {
  75.     color[a]=1;
  76.    
  77.         int s=W[a].size();
  78.         for (int ii=0; ii<s; ii++){
  79.             int i;
  80.             i=W[a][ii];
  81.             //if (m[a][i]!=0) {
  82.            
  83.                
  84.                 if (color[i]==0) {
  85.                 //  pr[ii]=a;
  86.                     DFSVISIT(i);
  87.                 }
  88.             //}
  89.         }
  90.         color[a]=2;
  91.        
  92.    
  93.         answer[counter]=a;
  94.         counter++;
  95. }
  96.  
  97.  
  98. void main(void)
  99. {
  100.   int a,b,c;
  101.   int M;
  102.   int MaxFlow,flow;
  103.   std::ifstream in("cut.in");
  104.   std::ofstream out("cut.out");
  105.  
  106.   memset(m,0,sizeof(m));
  107.  
  108.   in>>n>>M;
  109.  memset(color,0,sizeof(color));
  110.   source=0;
  111.   dest=n-1;
  112.    MaxFlow = 0;
  113.   for (int i=0; i<M; ++i)
  114.   {
  115.  
  116.       in >>a>>b>>c;
  117.       m[a-1][b-1] = c;
  118.         m[b-1][a-1] = c;
  119.         W[a-1].push_back(b-1);
  120.         W[b-1].push_back(a-1);
  121.  
  122.       if (c> Cmax) Cmax=c;
  123.   }
  124.  
  125. int k = 1;
  126.                while (k << 1 <= Cmax) {
  127.                        k <<= 1;
  128.                }
  129.  
  130.  
  131.  
  132.   for (int i = k; i >0; i >>= 1) {
  133.       z+=i;
  134.       while (1)
  135.       {
  136.         q.clear();
  137.         memset(p,-1,sizeof(p));
  138.         memset(used,0,sizeof(used));
  139.         memset(color,0,sizeof(color));
  140.         bfs(source);
  141.         flow = FindFlow(dest); if (flow > AAA) break;
  142.         MaxFlow += flow;
  143.         Rebuild(dest,flow);
  144.       }
  145.      // out<< z<< " ";
  146.   }
  147.   for (int i=0; i<n; i++) {
  148.       W[i].clear();
  149.   }
  150.   for (int i=0; i<n; i++) {
  151.       for (int j=0; j<n; j++) {
  152.           if (m[i,j]!=0) {
  153.              W[i].push_back(j);
  154.           }
  155.      }
  156.  
  157.   }
  158.  
  159.   DFSVISIT (0);
  160.   out<<counter<<"\n";
  161.   for (int i=0; i<counter-1;i++){ out << answer[i]+1<< " ";}
  162.   out << answer[counter-1]+1;
  163.  
  164.  
  165.  
  166.  
  167. }
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