#include #include #include using namespace std; constexpr int inf = 987654321; struct Edge { int dst, rev; int capa; }; class Graph { protected: int size; vector> g; public: Graph(int size) : size(size) { g.resize(size); } void add_edge(int src, int dst, int capa); int max_flow(int s, int t) { throw; } }; class Dinic : public Graph { vector level, iter; void bfs(int s); int dfs(int v, int t, int flow); public: Dinic(int size) : Graph(size) {} int max_flow(int s, int t); }; void Graph::add_edge(int src, int dst, int capa) { g[src].push_back(Edge({dst, int(g[dst].size()), capa})); g[dst].push_back(Edge({src, int(g[src].size())-1, 0})); } void Dinic::bfs(int s) { level.assign(size, -1); queue que; level[s] = 0; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for(Edge& e : g[v]) { if(e.capa > 0 && level[e.dst] < 0) { level[e.dst] = level[v] + 1; que.push(e.dst); } } } } int Dinic::dfs(int v, int t, int flow) { if(v == t) { return flow; } for(int& i=iter[v], n=g[v].size(); i= level[e.dst]) { continue; } int d = dfs(e.dst, t, min(flow, e.capa)); if(d > 0) { e.capa -= d; g[e.dst][e.rev].capa += d; return d; } } return 0; } int Dinic::max_flow(int s, int t) { int res = 0; while(true) { bfs(s); if(level[t] < 0) { return res; } iter.assign(size, 0); int flow; while((flow = dfs(s, t, inf)) > 0) { res += flow; if(res >= inf) { return inf; } } } } int main(void) { constexpr int N = 111; int n; scanf("%d", &n); Dinic graph(n + N*N + 2); int s = n + N*N, t = s + 1; for(int i=0; i