SHARE
TWEET

Untitled

gilzean May 22nd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <cmath>
  6. #include <cstring>
  7.  
  8. #define maxN 220
  9. #define eps 0.0000000000001
  10.  
  11. using namespace std;
  12.  
  13. long n,m,x,y,i;
  14. double c,flow;
  15. vector<long> list[maxN];
  16. double C[maxN][maxN],F[maxN][maxN];
  17.  
  18. queue<long> Q;
  19. long prov[maxN];
  20. bool used[maxN];
  21.  
  22. inline void addEdge(long x,long y,double c){
  23.     list[x].push_back(y);
  24.     list[y].push_back(x);
  25.  
  26.     C[x][y] = C[y][x] = c;
  27. }
  28.  
  29. bool BF(){
  30.     memset(used, 0, sizeof(used));
  31.     used[1] = true;
  32.     Q.push(1);
  33.     while (!Q.empty()){
  34.         long node = Q.front();
  35.         Q.pop();
  36.         if(node == n) {
  37.             continue;
  38.         }
  39.         for(long i = 0;i < list[node].size(); i++){
  40.             long newNode = list[node][i];
  41.             if(used[newNode] || C[node][newNode] - F[node][newNode] <= eps) {
  42.                 continue;
  43.             }
  44.             used[newNode] = true;
  45.             Q.push(newNode);
  46.             prov[newNode] = node;
  47.         }
  48.     }
  49.  
  50.     if(!used[n]) {
  51.         return false;
  52.     }
  53.  
  54.     for(long i = 0;i < list[n].size(); i++){
  55.         long dir = list[n][i];
  56.         if(!used[dir]) {
  57.             continue;
  58.         }
  59.  
  60.         prov[n] = dir;
  61.         double actFlow = 1000000000000000.00;
  62.         for(long node = n; node!=1; node = prov[node]) {
  63.             actFlow = min(actFlow, C[prov[node]][node] - F[prov[node]][node]);
  64.         }
  65.         for(long node = n;node != 1; node = prov[node]){
  66.             F[prov[node]][node] += actFlow;
  67.             F[node][prov[node]] -= actFlow;
  68.         }
  69.         flow += actFlow;
  70.     }
  71.  
  72.     return true;
  73. }
  74.  
  75. int main() {
  76.     cin >> n >> m;
  77.     for(i = 1; i <= m; i++){
  78.         cin >> x >> y >> c;
  79.         addEdge(x, y, log(c));
  80.     }
  81.  
  82.     for(;BF(););
  83.  
  84.     printf("%.4lf",exp(flow));
  85.  
  86.     return 0;
  87. }
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