首页 > > 程序设计 > C/C++ >

UOJ#179. 线性规划(线性规划)

2018-07-17 03:56:31来源：博客园阅读 ()

描述
提交
自定义测试

这是一道模板题。

（这个题现在标程挂了。。哪位哥哥愿意提供一下靠谱的标程呀？）

本题中你需要求解一个标准型线性规划：

有

此外这

在满足上述所有条件的情况下，你需要指定每个变量

输入格式

第一行三个正整数

第二行有

接下来

输出格式

如果不存在满足所有约束的解，仅输出一行 "Infeasible"。

如果对于任意的

否则，第一行输出一个实数，表示目标函数的最大值

如果

判断第二行是否合法时，我们首先检验

如果

样例一

input

output

4.2
1.8 2.4

explanation

两条约束分别为

当

样例二

input

output

4.0
4.0 0.0

explanation

注意

样例三

input

output

Infeasible

样例四

input

2 1 1
0 1
1 0 1

output

Unbounded

限制与约定

对于所有数据，

本题包含 4 个子任务，每个 25 分。

子任务 1,3 满足

子任务 2,4 没有特殊限制。

子任务 1,2 中

子任务 3,4 中

时间限制：

空间限制：

下载

样例数据下载

线性规划貌似在必修五有啊qwq不过还没学到估计也不会讲单纯形算法吧

感觉线性规划是差分约束的升级版？？

如果想学的话建议看2016年队爷的论文《浅谈线性规划在信息学竞赛中的应用》

不过为啥A不了啊

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 51, INF = 1e9 + 10;
const double eps = 1e-8;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
int N, M, opt;
int id[MAXN];
double ans[MAXN], a[MAXN][MAXN];
void Pivot(int l, int e) {
    swap(id[N + l], id[e]);
    double t = a[l][e]; a[l][e] = 1;
    for(int i = 0; i <= N; i++) a[l][i] /= t;//交换基变量与非基变量 
    for(int i = 0; i <= M; i++) {
        if(i != l && abs(a[i][e]) > eps) {
            t = a[i][e]; a[i][e] = 0;//t表示系数 
            for(int j = 0; j <= N; j++)
                a[i][j] -= a[l][j] * t;//消去需要消去的非基变量 
        }
    }//带入的过程就是消去非基变量 
}
bool init() {
    //寻找初始化解，若bi < 0，找到一个ai < 0，转换它们，不断重复直到所有的bi都 > 0
    //此时x1 = 0, x2 = 0···就是一组解 
    while(1) {
        int l = 0, e = 0;
        for(int i = 1; i <= M; i++) if(a[i][0] < -eps && (!l || (rand() & 1))) l = i;
        if(!l) break;
        for(int i = 1; i <= N; i++) if(a[l][i] < -eps && (!e || (rand() & 1))) e = i;
        if(!e) {puts("Infeasible"); return 0;}
        //这里所有的Xi都是正的，而bi是负的，这与松弛型相矛盾 
        Pivot(l, e);
    }
    return 1;
}
bool simplex() {
    while(1) {
        int l = 0, e = 0; double mn = INF;
        for(int i = 1; i <= N; i++)
            if(a[0][i] > eps) 
                {e = i; break;}
        if(!e) break;
        for(int i = 1; i <= M; i++)
            if(a[i][e] > eps && a[i][0] / a[i][e] < mn)
                mn = a[i][0] / a[i][e], l = i;//找到下界最紧的松弛 
        if(!l) {puts("Unbounded"); return 0;}
        Pivot(l, e);
    }
    return 1;
}
int main() {
    srand(19260817);
    N = read(); M = read(); opt = read();
    for(int i = 1; i <= N; i++) a[0][i] = read();//最大化C1X1 + C2X2··· 
    for(int i = 1; i <= M; i++) {
        for(int j = 1; j <= N; j++)
            a[i][j] = read();
        a[i][0] = read();// <= b 
    }
    for(int i = 1; i <= N; i++) id[i] =  i;
    if(init() && simplex()) {
        printf("%.8lf\n", -a[0][0]);
        if(opt) {
            for(int i = 1; i <= M; i++) ans[id[i + N]] = a[i][0];//tag
            for(int i = 1; i <= N; i++) printf("%.8lf ", ans[i]);
        }
    }
    return 0;
}
/*
3 3 1
3 1 2
1 1 3 30
2 2 5 24
4 1 2 36
*/