Back to : algorithms
Contents

## νμ΄

μ νμ μΈ ννμ Maximum Flow λ¬Έμ λ‘ μκ°ν  μ μλ€.

1. Sourceμ μ¬λ μ μ©λ λ¬΄νλμ κ°μ μΌλ‘ μλλ€.
2. μ¬λ μ κ° μκ°μ ν­μ 1λ§νΌμ© μΌμ ν  μ μμΌλ―λ‘, μ©λ 1μ κ°μ μΌλ‘ μ¬λ $m$κ° λΈλμ μκ° λΈλλ€μ λͺ¨λ μλλ€.
3. μκ° μλ κ°κ΅¬κ° 1λ§νΌ λ§λ€μ΄μ§ μ μμ§λ§, κ° κ°κ΅¬λ $[S_i, E_i]$ μ¬μ΄μλ§ λ§λ€μ΄μ§ μ μμΌλ―λ‘ μ΄λ₯Ό λ°μνμ¬ μ©λ 1λ§νΌμ κ°μ μ μλλ€.
4. κ°κ΅¬ κ°κ°μ $w_i$ λ§νΌμ© νλ‘μ°λ₯Ό λ°μμΌ νλ―λ‘, κ°κ΅¬ μ Sinkλ₯Ό μ©λ $w_i$ μ κ°μ μΌλ‘ μλλ€.

μ΄μ , Sourceμμ Sinkλ‘ νλ‘μ°λ₯Ό νλ €μ λμ°©νλ νλ‘μ°κ° $\sum w_i$ μ΄λ©΄ μ±κ³΅.

## μ½λ

μ‘°κΈ κΈ΄λ°, λ΄κ° μ½κ° κΈ΄ Dinic κ΅¬νμ²΄λ₯Ό μ΄λ€. Dinic μ½λλ Stanford ICPC Teamnote Libraryμμ κ°μ Έμλ€.

#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();
}
}