try_eval_p1.cpp

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <list>
#include <climits>
#include "graph.h"
using namespace std;

const double INF_DOUBLE = 1e20;

double loss_prob = 0.2;

vector<int> edges[NODE_NUM_MAX];
int weight[NODE_NUM_MAX];
int TW;
int n;  // tot node number
int in_deg[NODE_NUM_MAX];
double value[NODE_NUM_MAX];
int np = 1;  // tot package number
vector<int> pkgs[PKG_NUM_MAX];
vector<vector<int>> rst;

static double preset(int cur,int depth)
{
    static bool vis[NODE_NUM_MAX];
    if(edges[cur].empty())return 1;
    int s = edges[cur].size();
    double temp_val = 0;
    for(int i = 0;i < s;i++)
    {
        if(!vis[edges[cur][i]]){
            if(loss_prob > 0.3)temp_val += preset(edges[cur][i], depth+1)*pow(1-loss_prob, depth);         //1、丢包率小的情况下可以做改进。
                                                                                        //2、看前置的装的包的个数
            else temp_val += preset(edges[cur][i], depth+1) * (1-loss_prob);
            vis[edges[cur][i]] = true;
        }
        else temp_val += value[edges[cur][i]];
        
    }
    
    if(cur)value[cur] += temp_val;
    return temp_val;
}

void evaluate_nodes()
{
    // static int acc_w[NODE_NUM_MAX];
    // static int layer[NODE_NUM_MAX];
    // memset(acc_w, 255, sizeof(acc_w));
    // struct Node {
    //     int index;
    // };
    // vector<Node> *q = new vector<Node>;
    // vector<Node> *q2 = new vector<Node>;

    // acc_w[0] = 0;
    // q->push_back({0});
    // for (int h = 0; !q->empty(); ++h) {
    //     for (Node& node : *q) {
    //         int cur = node.index;
    //         for (int nxt : edges[cur]) {
    //             if (weight[nxt] == -1) {
    //                 acc_w[nxt] = weight[nxt] + acc_w[cur];
    //                 q->push_back({nxt});
    //             }
    //             else if (weight[nxt] + acc_w[cur] < acc_w[nxt]) {
    //                 acc_w[nxt] = weight[nxt] + acc_w[cur];
    //             }
    //         }
    //     }
    //     q->clear();
    //     swap(q, q2);
    // }

    // for (int x = 1; x <= n; ++x) {
    //     layer[x] = (acc_w[x] + PKG_SIZE - 1) / PKG_SIZE;
    //     value[x] = 10000. / weight[x] * pow(1 - loss_prob, layer[x]);
    // }
    preset(0, 0);
}

static int cnt[NODE_NUM_MAX];
struct Node {
    int index;
    int count;
    double value;
    bool operator< (const Node& n) const {
        return value < n.value;
    }
};
static priority_queue<Node> pq; // 大顶堆

static int tw2 = 0;
// static int cnt_debug[NODE_NUM_MAX];
void dfs_packaging_helper(int cur, int c)
{
    static int cur_weight_sum = 0;
    static bool vis[NODE_NUM_MAX] = {0};
    if (cur == 0)
        memset(vis, 0, sizeof(vis));

    for (int nxt : edges[cur]) {
        if (!vis[nxt] && c <= cnt[nxt]) {
            vis[nxt] = true;

            if (2 * (tw2 + weight[nxt]) > 3 * TW)
                break;

            if (cur_weight_sum + weight[nxt] <= PKG_SIZE) {
                /* 当前包的剩余容量够装 */
                cur_weight_sum += weight[nxt];
                pkgs[np].push_back(nxt);
            }
            else {
                /* 当前包的剩余容量不够装，开一个新的包 */
                cur_weight_sum = weight[nxt];
                pkgs[++np].push_back(nxt);
            }
            tw2 += weight[nxt];
            // ++cnt_debug[nxt];

            dfs_packaging_helper(nxt, c);
        }
    }
}

static int tw = 0;
void make_packages()
{
    /* Stage 1: decide which node(and how many times) to be packaged */
    pq.push({0,1,INF_DOUBLE});

    int flag = 1;

    static int cnt2[NODE_NUM_MAX];

    for (;;) {
        Node node = pq.top(); pq.pop();
        int cur = node.index;

        if ((tw + weight[cur]) * 2 > TW * 3)
            break;
        tw += weight[cur];

        ASSERT(cnt[cur] == node.count - 1);
        ++cnt[cur];
        for (int nxt : edges[cur]) {
            if (cnt2[nxt] < cnt[cur]) {
                ASSERT(cnt2[nxt] == cnt[cur]-1);
                pq.push({nxt, cnt[cur], value[nxt] * pow(loss_prob, cnt[cur]-1)});
                ++cnt2[nxt];
            }
        }
        
        /* 只要有非零的k层次节点被扩展，那么k+1层次的节点就要做好准备 */
        if (cur != 0 && cnt[cur] == flag) {
            flag += 1;
            pq.push({0,cnt[cur]+1,INF_DOUBLE});
        }
    }
    /* Stage 2: grouping */
    for (int c = 1; c < flag; ++c) {
        dfs_packaging_helper(0, c);
        ++np; // 要求两个层次的节点不能混装在一个包中
    }

    rst = vector<vector<int>>(pkgs+1, pkgs+np+1);
}

int main(int argc, char* argv[])
{
    if (LOG) {
        freopen("log.txt", "w", stdout);
    }
    char *edge_path, *weight_path, *answer_path;
    if (argc == 5) {
        edge_path = argv[1];
        weight_path = argv[2];
        answer_path = argv[3];
        loss_prob = atoi(argv[4]) / 100.;
    }
    else {
        edge_path = (char *)"data/Out_OutGraph_Basketball_480_Slice16_Gop8_10.log";
        weight_path = (char *)"data/Out_SliceSize_Basketball_480_Slice16_Gop8_10.log";
        answer_path = (char *)"result.txt";
        loss_prob = 0.2;
    }

    read_graph(edge_path, weight_path); debug_printf("TW = %d\n", TW);
    evaluate_nodes();
    make_packages();
    printf("np = %d, rst.size() = %u\n", np, rst.size());
    printf("tw = %d, tw2 = %d\n", tw, tw2);
    output(answer_path);
    // for (int i = 1; i <= n; ++i) {
    //     if (cnt[i] != cnt_debug[i])
    //         printf("cnt[%d] = %d, cnt_debug[%d] = %d\n", i, cnt[i], i, cnt_debug[i]);
    // }
    return 0;
}