BOJ 8904, ICPC Korea 2011 가구 공장

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

struct Edge
{
    int u, v;
    ll cap, flow;
    Edge() {}
    Edge(int u, int v, ll cap): u(u), v(v), cap(cap), flow(0) {}
};

struct Dinic
{
    int N;
    vector<Edge> E;
    vector<vector<int>> g;
    vector<int> d, pt;

    Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {}

    void AddEdge(int u, int v, ll cap)
    {
        if (u != v)
        {
            E.push_back(Edge(u, v, cap));
            g[u].push_back(E.size() - 1);
            E.push_back(Edge(v, u, 0));
            g[v].push_back(E.size() - 1);
        }
    }

    bool BFS(int S, int T)
    {
        queue<int> q({S});
        fill(d.begin(), d.end(), N + 1);
        d[S] = 0;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            if (u == T) break;
            for (int k: g[u])
            {
                Edge &e = E[k];
                if (e.flow < e.cap && d[e.v] > d[e.u] + 1)
                {
                    d[e.v] = d[e.u] + 1;
                    q.push(e.v);
                }
            }
        }
        return d[T] != N + 1;
    }

    ll DFS(int u, int T, ll flow = -1)
    {
        if (u == T || flow == 0) return flow;
        for (int &i = pt[u]; i < g[u].size(); i++)
        {
            Edge &e = E[g[u][i]];
            Edge &oe = E[g[u][i]^1];
            if (d[e.v] == d[e.u] + 1)
            {
                ll amt = e.cap - e.flow;
                if (flow != -1 && amt > flow) amt = flow;
                if (ll pushed = DFS(e.v, T, amt))
                {
                    e.flow += pushed;
                    oe.flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    ll MaxFlow(int S, int T)
    {
        ll total = 0;
        while (BFS(S, T))
        {
            fill(pt.begin(), pt.end(), 0);
            while (ll flow = DFS(S, T))
                total += flow;
        }
        return total;
    }
};

// SOURCE = 0
// PERSON = 1 - 10
// TIME = 101 - 100 + max(di) <= 600
// Furn = 601 - 700
// SINK = 11
void solve()
{
    int SINK = 11;
    int SOURCE = 0;
    int BIG = 10000;
    Dinic D(701);
    int m, n; cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        D.AddEdge(SOURCE, i, BIG);
        for (int j = 1; j <= 500; j++)
        {
            D.AddEdge(i, j + 100, 1);
        }
    }
    int tw = 0;
    for (int i = 1; i <= n; i++)
    {
        int s, w, d;
        cin >> s >> w >> d;
        for (int j = s; j < d; j++)
            D.AddEdge(j + 100, 600 + i, 1);
        D.AddEdge(600 + i, SINK, w);
        tw += w;
    }
    int f = D.MaxFlow(SOURCE, SINK);
    if (f != tw)
    {
        cout << 0 << '\n';
        return;
    }
    list <pii> fr[101];
    for (Edge e : D.E)
    {
        if (e.flow == 1)
            if (100 <= e.u and e.u <= 600)
                if (601 <= e.v)
                    fr[e.v - 600].push_back({e.u - 100, e.u - 99});
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto it = fr[i].begin(); it != fr[i].end();)
        {
            if (it == fr[i].begin())
            {
                it++; continue;
            }
            auto bef = it; bef--;
            if (it->first == (bef)->second)
            {
                (bef)->second = it->second;
                it = fr[i].erase(it);
            }
            else it++;
        }
        cout << fr[i].size() << ' ';
        for (pii pp : fr[i])
        {
            cout << pp.first << ' ' << pp.second << ' ';
        }
        cout << '\n';
    }
    return;
}
int32_t main()
{
    usecppio
    int T; cin >> T;
    while(T--)
    {
        solve();
    }
}