首页 > 代码库 > 单纯性与网络流
单纯性与网络流
单纯性模板:
需要b > 0, xi > 0.
1 // 单纯性 2 // n+1 * m+1 矩阵 3 // 1~n 为约束 <= 右值 4 // n+1为目标最大值 5 // 对偶化直接转置即可 6 const int maxn = 1100, maxm = 11000; 7 const double eps = 1e-7, INF = 1e20; 8 int dcmp(double a) { return fabs(a)<eps?0:a<0?-1:1; } 9 int n , m; 10 double a[maxm][maxn]; 11 void pivot(int l , int e){ 12 for(int i = 1; i <= n; i++) if(i != l&&dcmp(a[i][e])){ 13 for(int j = 1; j <= m; j++) 14 if(j != e) a[i][j] -= a[i][e]/a[l][e]*a[l][j]; 15 a[i][e] /= -a[l][e]; 16 } 17 for(int i = 1; i <= m; i++) if(i != e) a[l][i] /= a[l][e]; a[l][e] = 1/a[l][e]; 18 } 19 20 double simplex(){ 21 double mn; 22 int e , l; 23 while(1){ 24 for(e=1;e<m;e++) if(dcmp(a[n][e]) > 0) break; 25 if(e == m) return -a[n][m]; 26 mn = INF; 27 for(int i=1;i<n;i++) if(dcmp(a[i][e]) > 0 && mn > a[i][m]/a[i][e]) mn = a[l=i][m]/a[i][e]; 28 if(mn == INF) return INF; 29 pivot(l, e); 30 } 31 }
bzoj1061
题意:有n天,第i天需要ai个志愿者,有m类志愿者,每类志愿者工作时间为[l,r],花费为ci,求最小花费
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1100, maxm = 11000; 5 const double eps = 1e-7, INF = 1e20; 6 int dcmp(double a) { return fabs(a)<eps?0:a<0?-1:1; } 7 int n , m; 8 double a[maxm][maxn]; 9 void pivot(int l , int e){ 10 for(int i = 1; i <= n; i++) if(i != l&&dcmp(a[i][e])){ 11 for(int j = 1; j <= m; j++) 12 if(j != e) a[i][j] -= a[i][e]/a[l][e]*a[l][j]; 13 a[i][e] /= -a[l][e]; 14 } 15 for(int i = 1; i <= m; i++) if(i != e) a[l][i] /= a[l][e]; a[l][e] = 1/a[l][e]; 16 } 17 18 double simplex(){ 19 double mn; 20 int e, l; 21 while(1){ 22 for(e=1;e<m;e++) if(dcmp(a[n][e]) > 0) break; 23 if(e == m) return -a[n][m]; 24 mn = INF; 25 for(int i=1;i<n;i++) if(dcmp(a[i][e]) > 0 && mn > a[i][m]/a[i][e]) mn = a[l=i][m]/a[i][e]; 26 if(mn == INF) return INF; 27 pivot(l, e); 28 } 29 } 30 31 int main() { 32 scanf("%d%d", &n, &m); 33 //对偶化 34 for(int i = 1; i <= n; i++) 35 scanf("%lf", &a[m+1][i]); 36 for(int i = 1, l, r, v; i <= m; i++) { 37 scanf("%d%d%d" , &l, &r, &v); 38 for(int j = l; j <= r; j++) a[i][j] = 1; 39 a[i][n+1] = v; 40 } 41 n++, m++; 42 swap(n, m); 43 printf("%d" , (int)(simplex()+0.50)); 44 return 0; 45 }
单纯性与网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。