Yhdistelmät

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <random>
#include <set>
#include <vector>
using namespace std;

namespace {
// Source: https://github.com/jaehyunp/stanfordacm/blob/master/code/Simplex.cc

// Two-phase simplex algorithm for solving linear programs of the form
//
//     maximize     c^T x
//     subject to   Ax <= b
//                  x >= 0
//
// INPUT: A -- an m x n matrix
//        b -- an m-dimensional vector
//        c -- an n-dimensional vector
//        x -- a vector where the optimal solution will be stored
//
// OUTPUT: value of the optimal solution (infinity if unbounded
//         above, nan if infeasible)
//
// To use this code, create an LPSolver object with A, b, and c as
// arguments.  Then, call Solve(x).

//typedef long double DOUBLE;
typedef double DOUBLE;
typedef vector<DOUBLE> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;

const DOUBLE EPS = 1e-9;

struct LPSolver {
    int m, n;
    VI N, B;
    VVD D;

    LPSolver(const VVD &A, const VD &b, const VD &c) :
        m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
        for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
        for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
        N[n] = -1; D[m + 1][n] = 1;
    }

    void Pivot(int r, int s) {
        double inv = 1.0 / D[r][s];
        for (int i = 0; i < m + 2; i++) if (i != r)
            for (int j = 0; j < n + 2; j++) if (j != s)
                D[i][j] -= D[r][j] * D[i][s] * inv;
        for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] *= inv;
        for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] *= -inv;
        D[r][s] = inv;
        swap(B[r], N[s]);
    }

    bool Simplex(int phase) {
        int x = phase == 1 ? m + 1 : m;
        while (true) {
            int s = -1;
            for (int j = 0; j <= n; j++) {
                if (phase == 2 && N[j] == -1) continue;
                if (s == -1 || D[x][j] < D[x][s] || (D[x][j] == D[x][s] && N[j] < N[s])) s = j;
            }
            if (D[x][s] > -EPS) return true;
            int r = -1;
            for (int i = 0; i < m; i++) {
                if (D[i][s] < EPS) continue;
                if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
                    ((D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r])) r = i;
            }
            if (r == -1) return false;
            Pivot(r, s);
        }
    }

    DOUBLE Solve(VD &x) {
        int r = 0;
        for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
        if (D[r][n + 1] < -EPS) {
            Pivot(r, n);
            if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
            for (int i = 0; i < m; i++) if (B[i] == -1) {
                int s = -1;
                for (int j = 0; j <= n; j++)
                    if (s == -1 || D[i][j] < D[i][s] || (D[i][j] == D[i][s] && N[j] < N[s])) s = j;
                  Pivot(i, s);
            }
        }
        if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
        x = VD(n);
        for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
        return D[m][n + 1];
    }
};
}

struct Problem {
    vector<int> P;
    vector<int> X;
    vector<vector<int>> groups;
};

vector<int> solve(Problem prob) {
    const auto& P = prob.P;
    const auto& X = prob.X;
    const auto& groups = prob.groups;
    int n = P.size();
    int m = X.size();
    VVD A;
    for (int i=0; i<n; i++) {
        VD row(n+m);
        row[i] = 1;
        A.push_back(move(row));
    }
    for (int i=0; i<m; i++) {
        for (int id:groups[i]) {
            VD row(n+m);
            row[n+i] = 1;
            row[id] = -1;
            A.push_back(move(row));
        }
    }
    VD b(A.size());
    for (int i=0; i<n; i++) b[i] = 1;
    VD c(n+m);
    for (int i=0; i<n; i++) c[i] = -P[i] + 1e-4;
    for (int i=0; i<m; i++) c[n+i] = X[i];

    LPSolver solver(A, b, c);
    VD x;
    solver.Solve(x);
    vector<int> ans;
    for (int i=0; i<n; i++) {
        if (x[i] > 0.5) {
            ans.push_back(i);
        }
    }
    return ans;
}

int get_value(const Problem& prob, const vector<int>& ans) {
    int value = 0;
    for (int id : ans) {
        value -= prob.P[id];
    }
    set<int> S(ans.begin(), ans.end());
    for (int i=0; i<(int)prob.X.size(); i++) {
        bool ok = true;
        for (int id : prob.groups[i]) {
            ok &= S.count(id);
        }
        if (ok) {
            value += prob.X[i];
        }
    }
    return value;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin>>n>>m;
    vector<int> P(n); for (int&x:P) cin>>x;
    vector<int> X(m);
    vector<vector<int>> groups(m);
    for (int i=0; i<m; i++) {
        int k; cin>>k>>X[i];
        groups[i].resize(k);
        for (int& id:groups[i]) cin>>id, id--;
    }

    Problem prob{P, X, groups};
    vector<int> ans = solve(prob);
    int sum = get_value(prob, ans);
    int len = ans.size();

    cout << sum << '\n';
    cout << len << '\n';
    for (int i=0; i<len; i++) {
        cout << (ans[i]+1) << " \n"[i+1==len];
    }
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 4

Verdict: ACCEPTED

Test 4

Group: 1, 4

Verdict: ACCEPTED

Test 5

Group: 1, 4

Verdict: ACCEPTED

Test 6

Group: 1, 4

Verdict: ACCEPTED

Test 7

Group: 1, 4

Verdict: ACCEPTED

Test 8

Group: 1, 4

Verdict: ACCEPTED

Test 9

Group: 1, 4

Verdict: ACCEPTED

Test 10

Group: 1, 4

Verdict: ACCEPTED

Test 11

Group: 2, 3, 4

Verdict: ACCEPTED

Test 12

Group: 3, 4

Verdict: ACCEPTED

Test 13

Group: 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED

Test 17

Group: 4

Verdict: ACCEPTED

Test 18

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 19

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 20

Group: 4

Verdict: ACCEPTED

Test 21

Group: 4

Verdict: ACCEPTED