首页 > 代码库 > bzoj1061&&bzoj3256

bzoj1061&&bzoj3256

2024-09-22 01:31:45   218人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1061

单纯形。。。

先开始我不知道对偶，看着代码不知所措，并不能懂他们写的是什么。。。

单纯形的标准形式是uoj上那样的，限制小于，最大化，但是这道题是最小化，而且系数取负还不行（我的理解是取负了无法正常运行），那么我们引入了对偶

对偶其实就是把矩阵转一下 a[i][j]=b[j][i] swap(n,m)就好了，然后跑单纯形。。。

技术分享 
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const double eps = 1e-8;
int n, m, l, e;
double a[N * 10][N], b[N][N * 10];
void pivot(int l, int e)
{
    double r = a[l][e]; a[l][e] = 1.0;
    for(int i = 0; i <= m; ++i) a[l][i] /= r;
    for(int i = 0; i <= n; ++i) if(i != l)
    {
        double r = a[i][e]; a[i][e] = 0;
        for(int j = 0; j <= m; ++j) a[i][j] -= r * a[l][j];
    }
} 
void simplex()
{
    while(true) 
    {
        l = e = 0;
        for(int i = 1; i <= m; ++i) if(a[0][i] > eps) 
        { e = i; break; }
        if(!e) break;
        double k = 1e18;
        for(int i = 1; i <= n; ++i) if(a[i][e] > eps && a[i][0] / a[i][e] < k)
        {
            k = a[i][0] / a[i][e];
            l = i;
        }
        if(!l) break; 
        pivot(l, e);    
    }
    printf("%d\n", (int)(-a[0][0] + 0.5)); 
}
int main()
{
//    freopen("employee.in", "r", stdin);
//    freopen("employee.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%lf", &b[i][0]);
    for(int i = 1; i <= m; ++i)
    {
        int s, t; double c; scanf("%d%d%lf", &s, &t, &c);
        for(int j = s; j <= t; ++j) b[j][i] += 1.0;
        b[0][i] += c;
    }
    swap(n, m);
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j) a[i][j] = b[j][i];
    simplex();
//    fclose(stdin); fclose(stdout);
    return 0;
}
View Code

 

bzoj1061&&bzoj3256


联系
我们