首页 > 代码库 > 全局最小割模版 n^3

全局最小割模版 n^3

2024-08-01 10:26:14   216人阅读

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. //点标从0-n-1, 开始时先init 复杂度n^3  
  2. //对于边(u,v,flow):  
  3. //g[u][v]+=flow;  
  4. //g[v][u]+=flow;  
  5. typedef long long ll;  
  6. const int N = 305;  
  7. const ll inf = 1e18;  
  8. ll g[N][N], w[N];  
  9. int a[N], v[N], na[N];  
  10. ll mincut(int n) {  
  11.     int i, j, pv, zj;  
  12.     ll best = inf;  
  13.     for(i = 0; i < n; i ++) v[i] = i;  
  14.   
  15.     while(n > 1) {  
  16.         for(a[v[0]] = 1, i = 1; i < n; i ++) {  
  17.             a[v[i]] = 0;  
  18.             na[i-1] = i;  
  19.             w[i] = g[v[0]][v[i]];  
  20.         }  
  21.         for(pv = v[0], i = 1; i < n; i ++) {  
  22.             for(zj = -1, j = 1; j < n; j ++)  
  23.                 if(!a[v[j]] && (zj < 0 || w[j] > w[zj])) zj = j;  
  24.   
  25.             a[v[zj]] = 1;  
  26.             if(i == n-1) {  
  27.                 if(best > w[zj]) best = w[zj];  
  28.                 for(i = 0; i < n; i ++) {  
  29.                     g[v[i]][pv] = g[pv][v[i]] += g[v[zj]][v[i]];  
  30.                 }  
  31.                 v[zj] = v[--n];  
  32.                 break;  
  33.             }  
  34.             pv = v[zj];  
  35.             for(j = 1; j < n; j ++) if(!a[v[j]])  
  36.                 w[j] += g[v[zj]][v[j]];  
  37.         }  
  38.     }  
  39.     return best;  
  40. }  
  41. void init(int n){  
  42.     for(int i = 0; i < n; i ++)  
  43.         for(int j = 0; j < n; j ++)  
  44.             g[i][j] = g[j][i] = 0;  
  45. } 

全局最小割模版 n^3


联系
我们