Code

Code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define cst(T) const T&

template<class A, class B> bool umin(A& var, cst(B) val) {
    return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
    return (var < val) ? (var = val, true) : false;
}

typedef long long Int;
typedef long double Real;
const int MOD = 2004010501;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> Int random(const X& l, const Y& r) {
    return uniform_int_distribution<Int>(l,r)(rng);
}
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';

template<typename T> vector<T> readInput(int n) {
    vector<T> v(n); for (auto &vi : v) cin >> vi; return v;
}

//DATA
const int N = 1050;
int numNodes, numEdges;
int requiredValue;
struct Edge {
    int from, to, cost, value;
};
Edge edges[N];
int numSpecials;
vector<int> specials;
vector<int> adj[N]; //for v=1 case, save edge's id

class DisjointSet {
private :
    int size; vector<int> label;
public :
    void reset() { label.assign(size+1, -1); }
    int getSize(void) const { return size; }
    DisjointSet(int size) : size(size) {
        reset();
    }

    int find_root(int u) {
        if (label[u] < 0) return u;
        return label[u] = find_root(label[u]);
    }

    bool merge_set(int u, int v) {
        u = find_root(u), v = find_root(v);
        if (u == v) return false;
        if (-(label[u]) < -(label[v])) swap(u,v);
        label[u] += label[v], label[v] = u;
        return true;
    }

    bool same_set(int a, int b) { 
        return find_root(a) == find_root(b);
    }
}; 

class Solution {
private:
    string conf;
public:
    int cost = 0, val = 0;
    Solution() { conf.assign(numEdges, '0'); }

    const string& getConf(void) const { return conf; }
    bool operator< (const Solution& rhs) const {
        return cost < rhs.cost;
    }

    void fill1(void);
    void flip(int i);
    int eval(void);
};

void input(); //read problem's input
void output(cst(Solution) sol); //print the best configuration found

void Solution::fill1(void) {
    conf.assign(numEdges, '1');
    for (int i = 1; i <= numEdges; i++) {
        cost += edges[i].cost;
        val += edges[i].value;
    }
}

void Solution::flip(int i) {
    if (conf[i] == '0') {
        conf[i] = '1';
        cost += edges[i+1].cost;
        val += edges[i+1].value;
    }
    else {
        conf[i] = '0';
        cost -= edges[i+1].cost;
        val -= edges[i+1].value;
    }
}

const int INF = 1e9;
int Solution::eval(void) {
    auto& res = this->cost;
    if (this->val < requiredValue) return res = INF;
    static DisjointSet dsu(0);
    if (!dsu.getSize()) dsu = DisjointSet(numNodes);
    dsu.reset();
    for (int i = 1; i <= numEdges; i++)
        if (this->conf[i-1] == '1')
            dsu.merge_set(edges[i].from, edges[i].to);
    for (auto u : specials)
        if (!dsu.same_set(u, specials[0])) return res = INF;
    return res;
}

void input() {
    cin >> numNodes >> numEdges >> numSpecials >> requiredValue;
    for (int i = 1; i <= numEdges; i++) {
        int x,y,c,v;
        cin >> x >> y >> c >> v;
        edges[i] = {x,y,c,v};
    }
    specials.resize(numSpecials);
    for (auto& u : specials) cin >> u;
    //for v = 1
    for (int i = 1; i <= numEdges; i++) {
        auto [x,y,c,v] = edges[i];
        adj[x].push_back(i);
        adj[y].push_back(i);
    }
}

void output(cst(Solution) sol) {
    string conf = sol.getConf();
    vector<int> edge_ids;
    for (int i = 0; i < numEdges; i++)
        if (conf[i] == '1') edge_ids.push_back(i+1);
    cout << sol.cost << '\n';
    cout << edge_ids.size() << ' ';
    for (auto id : edge_ids) cout << id << ' ';
    cout << '\n';
}

// Define the random number generator
random_device rd;
mt19937 gen(rd());
uniform_real_distribution<double> dis(0.0, 1.0);
//Usage: dis(gen)

const double initialTemp = 1e9;
const double coolingRate = 1e-4;
const double finishTemp = 1e-6;

Real acceptProb(int cur, int nxt, Real temp) {
    if (nxt < cur) return 1;
    return exp((cur-nxt) / temp); //negative
}

void solve(int testID) {
    DBGn(testID);
    input();

    Solution best;
    best.fill1();

    auto start = chrono::steady_clock::now();

    const double timeLimit = 180;
    double temp = initialTemp;

    Solution cur(best), next(cur);
    /*
    By FakePsyho:
    #12: Standard SA:
    temp schedule: t = t_start * (t_final / t_start) ^ time_passed, where time_passed is in 0..1
    acceptance (when min is better): RNG() < exp((cur_result - new_result) / t), where RNG() returns 0..1 uniformly

    It's the best starting point in almost all cases
    */
    Real lastTime = 0;
    while (temp > finishTemp) {
        auto now = chrono::steady_clock::now();
        auto elapsedTime = chrono::duration_cast<chrono::seconds>(now-start).count();
        temp = initialTemp * pow(finishTemp / initialTemp, elapsedTime / timeLimit);
        // if (elapsedTime > timeLimit) break;
        if (elapsedTime > lastTime && ((int) elapsedTime % 25 <= 1)) {
            lastTime = elapsedTime;
            cerr << elapsedTime << ", " << cur.cost << "| ";
        }

        int numSteps = random(1, 5);
        for (int i = 0; i < numSteps; i++)
            next.flip(random(0, numEdges-1));

        if (next.eval() < INF && acceptProb(cur.cost, next.cost, temp) >= dis(gen))
            cur = next;
        else next = cur;

        if (cur.cost < best.cost) best = cur;

        // temp *= 1 - coolingRate;
        //cooling schedule generated by ChatGPT
        /*
        double fraction = 1.0 - elapsedTime / timeLimit;
        double alpha = -log(fraction) / timeLimit;
        temp *= exp(-alpha * elapsedTime);
        */
    }
    cerr << "\\\\ Result = " << best.cost << '\n';
    output(best);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define task "WF"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve(1);
}