这难道不是单纯形的题目吗?蒟蒻只会单纯形...

###为了做这题我还特意去学习了单纯形.好难啊!听说别的神犇都推了好多数学结论,我打表看了一天愣是什么都没看出来...

测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
Accepted, time = 0 ms, mem = 580 KiB, score = 100

###代码:

#include <bits/stdc++.h>
const double eps = 1e-8;
double a[10][10];
int ans[10], n, m, A, B;

void pivot (int k, int x) {
    ans[k] = x;

    double t = -a[k][x]; a[k][x] = 0;
    for (int i = 0; i <= n + m; ++ i)
        a[k][i] /= t;

    for (int i = 0; i <= m; a[i][x] = 0, ++ i)
        for (int j = 0; j <= n + m; ++ j)
            a[i][j] += a[i][x] * a[k][j];
    a[k][x] = -1;
}

void simplex () {
    int k, x;
    while (1) {
        k = x = 0;
        for (int i = 1; i <= m; ++ i)
            if (a[i][0] < -eps) { k = i; if (rand () & 1) break; }
        if (!k) break;

        for (int i = 1; !x && i <= n + m; ++ i)
            if (eps < a[k][i]) x = i;

        pivot (k, x);
    }

    double mx;
    while (1) {
        k = x = 0; mx = 1e9;
        for (int i = 1; i <= n + m; ++ i)
            if (eps < a[0][i]) { x = i; if (rand () & 1) break; }
        if (!x) break;

        for (int i = 1; i <= m; ++ i)
            if (ans[i] != x && a[i][x] < -eps && a[i][0] / -a[i][x] < mx)
                mx = a[i][0] / -a[i][x], k = i;

        pivot (k, x);
    }

    printf ("%.0lf\n", a[0][0]);
}

int main () {
    scanf ("%d %d", &A, &B), n = 2, m = 2;
    a[0][1] = 1;
    a[1][0] = A + B, a[1][1] = 1;
    a[2][0] = -a[1][0], a[2][1] = 1;
    for (int i = 1; i <= m; ++ i) ans[i] = n + i;

    simplex ();

    return 0;
}

4 条评论

  • @ 2017-01-19 09:05:28

    呵呵呵......(看一群人在这胡扯)

  • @ 2016-11-03 21:15:18

    单纯形是这题最简单的做法了,你还算运气好打了单纯形,不然一个月也难得A。

  • @ 2016-11-03 21:10:33

    你看不出来也很正常,我尝试推导过这题的结论,根本推不动,听说这题难度绝非国王饮水记之流可比。

  • @ 2016-11-03 21:10:30

    你看不出来也很正常,我尝试推导过这题的结论,根本推不动,听说这题难度绝非国王饮水记之流可比。

  • 1

信息

ID
1000
难度
9
分类
(无)
标签
(无)
递交数
73498
已通过
28189
通过率
38%
被复制
200