Prelude
传送到LOJ
又一道不会做的题。。。
这题其实就是最小路径覆盖。
Solution
就是先写一个循环，把当前循环变量\(i\)的出点与满足条件的更小的数\(j\)的入点连边，其余类似于最小路径覆盖。
当最少路径数比\(n\)大时，输出\(i-1\)，输出方案我在这里也用了链表，每循环一次更新一次。。。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; const int MAXN = 50000; const int MAXM = 200000; const int INF = 0x3f3f3f3f; namespace Dinic { struct Edge { int u,v,c,f; Edge() {} Edge(int u,int v,int c,int f): u(u), v(v), c(c), f(f) {} }; int n,m,s,t; int head[MAXN], nxt[MAXM]; int dist[MAXN], cur[MAXN]; Edge edge[MAXN]; void clear(int _n) { n = _n, m = 0; for(int i = 0; i < n; ++i) head[i] = -1; } void addedge(int u,int v,int c) { edge[m] = Edge(u,v,c,0); nxt[m] = head[u]; head[u] = m++; edge[m] = Edge(v,u,0,0); nxt[m] = head[v]; head[v] = m++; } queue<int> q; bool bfs() { for(int i = 0; i < n; ++i) dist[i] = INF; dist[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dist[e.v] == INF) { dist[e.v] = dist[u] + 1; q.push(e.v); } } } return dist[t] != INF; } int dfs(int u,int res) { if(u == t || !res) return res; int flow = 0, f; for(int &i = cur[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dist[e.v] == dist[u] + 1) { f = dfs(e.v,min(res,e.c - e.f)); e.f += f; edge[i^1].f -= f; flow += f; res -= f; if(!res) break; } } return flow; } int maxflow(int _s, int _t) { s = _s, t = _t; int flow = 0; while(bfs()) { for(int i = 0; i < n; ++i) cur[i] = head[i]; flow += dfs(s,INF); } return flow; } } bool check(int x) { int sq = sqrt(x); if(sq*sq == x) return 1; return 0; } struct node { int num; bool last; node *next; }ans[MAXN]; int main() { int n; scanf("%d",&n); int s = 0, t = 9000; Dinic::clear(t + 1); int flow = 0; for(int i = 1;;++i) { for(int j = 1; j < i; ++j) if(check(j+i)) Dinic::addedge((j<<1)-1,(i<<1),1); Dinic::addedge(s,(i<<1)-1,1); Dinic::addedge((i<<1),t,1); flow += Dinic::maxflow(s,t); if(i-flow > n) { printf("%d\n",i-1); for(int j = 1; j < i; ++j) { if(ans[j].last) continue; for(node *u = &ans[j]; u; u = u->next) printf("%d ",u->num); puts(""); } return 0; } for(int j = 1; j <= i; ++j) { ans[i].last = 0; ans[i].next = NULL; ans[i].num = i; } for(int j = 0; j < Dinic::m; ++j) { if(Dinic::edge[j].u == s || Dinic::edge[j].u == t || Dinic::edge[j].v == s || Dinic::edge[j].v == t) continue; if(Dinic::edge[j].f == 1) { ans[(Dinic::edge[j].u + 1) >> 1].next = &ans[(Dinic::edge[j].v + 1) >> 1]; ans[(Dinic::edge[j].v + 1) >> 1].last = 1; } } } return 0; } |