testtest.cpp

/*
    Algorithm : Dinic's Algorithm For Max Flow
    0-indexed node numbering(0, 1, 2, ..., n-1)
    s - source node
    t - destination node
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int INF = 1000000000;

struct edge {
    int a, b, cap, flow;
};
int cnt[27], letter;
int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
vector<edge> e;
vector<int> g[MAXN];

void add_edge(int u, int v, int cap)
{
    edge e1 = {u, v, cap, 0};
    edge e2 = {v, u, 0, 0};
    g[u].push_back((int)e.size());
    e.push_back(e1);
    g[v].push_back((int)e.size());
    e.push_back(e2);
}

bool bfs()
{
    int qh = 0, qt = 0;
    q[qt++] = s;
    memset (d, -1, n * sizeof d[0]);
    d[s] = 0;
    while(qh < qt && d[t] == -1){
        int v = q[qh++];
        for(size_t i =0; i<g[v].size(); ++i){
            int id = g[v][i], to = e[id].b;
            if(d[to] == -1 && e[id].flow < e[id].cap){
                q[qt++] = to;
                d[to] = d[v] + 1;
            }
        }
    }
    return d[t] != -1;
}

int dfs(int v, int flow)
{
    if(!flow) return 0;
    if(v == t) return flow;
    for(; ptr[v] < (int)g[v].size(); ++ptr[v]){
        int id = g[v][ptr[v]], to = e[id].b;
        if(d[to] != d[v]+1) continue;
        int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
        if(pushed){
            e[id].flow += pushed;
            e[id^1].flow -= pushed;
            return pushed;
        }
    }
    return 0;
}

int dinic()
{
    int flow = 0;
    for(;;){
        if(!bfs()) break;
        memset(ptr, 0, n*sizeof ptr[0]);
        while(int pushed = dfs(s, INF)){
            flow += pushed;
        }
    }
    return flow;
}

void prep()
{
    for(int i=0; i<MAXN; i++){
        g[i].clear();
    }
    e.clear();
}

void build(int st)
{
    s = 0, t = 26 + letter + 1;
    n = t+1;
    for(int i=1; i<=26; i++){
        add_edge(s, i, cnt[i]);
    }
    for(int i=st; i<=letter; i++){
        int nodeNum = i+26;
        add_edge(nodeNum, t, 1);
        for(int j=1; j<=26; j++){
            if(i%j == 0 && cnt[j]){
                add_edge(j, nodeNum, 1);
            }
        }
    }
}

int main()
{
    int cases;
    scanf("%d", &cases);
    while(cases--){
        scanf("%d", &letter);
        for(int i=1; i<=26; i++){
            scanf("%d", &cnt[i]);
        }
        int ans[letter];
        prep();
        build(1);
        if(dinic() == letter){
            for(int i=1; i<=letter; i++){
                for(int j=1; j<=26; j++){
                    if(cnt[j]){
                        if(i % j == 0){

                        }
                    }
                }
            }
        }
    }
}