魔术球问题 【网络流24题】【建图技巧】

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 200007;
 49 
 50 int n, m;
 51 int s, t;
 52 
 53 struct edge{
 54     int from,to;
 55     LL cap,flow;
 56 };
 57 
 58 int Pre[maxn << 1], Nxt[maxn << 1];
 59 bool vis[maxn << 1];
 60 
 61 struct DINIC {
 62     int head[maxn << 1], nxt[maxn << 1], edge[maxn << 1], cnt;
 63     int cap[maxn << 1], depth[maxn << 1];
 64 
 65     void init() {
 66         cnt = 1;
 67         memset(head, 0, sizeof(head));
 68     }
 69 
 70     void BuildGraph(int u, int v, int w) {
 71         ++cnt;
 72         edge[cnt] = v;
 73         nxt[cnt] = head[u];
 74         cap[cnt] = w;
 75         head[u] = cnt;
 76 
 77         ++cnt;
 78         edge[cnt] = u;
 79         nxt[cnt] = head[v];
 80         cap[cnt] = 0;
 81         head[v] = cnt;
 82     }
 83 
 84     queue<int> q;
 85 
 86     bool bfs() {
 87         memset(depth, 0, sizeof(depth));
 88         depth[s] = 1;
 89         q.push(s);
 90         while(!q.empty()) {
 91             int u = q.front();
 92             q.pop();
 93             for ( int i = head[u]; i; i = nxt[i] ) {
 94                 int v = edge[i];
 95                 if(depth[v]) {
 96                     continue;
 97                 }
 98                 if(cap[i]) {
 99                     depth[v] = depth[u] + 1;
100                     q.push(v);
101                 }
102             }
103         }
104         return depth[t];
105     }
106 
107     int dfs(int u, int dist) {
108         if(u == t) {
109             return dist;
110         }
111         int flow = 0;
112         for ( int i = head[u]; i && dist; i = nxt[i] ) {
113             if(cap[i] == 0)
114                 continue;
115             int v = edge[i];
116             if(depth[v] != depth[u] + 1) {
117                 continue;
118             }
119             int res = dfs(v, min(cap[i], dist));
120             cap[i] -= res;
121             cap[i ^ 1] += res;
122             //printf("cap[%d]:%d\n",t, cap[t]);
123             dist -= res;
124             flow += res;
125             Nxt[u / 2] = v / 2;
126         }
127         return flow;
128     }
129 
130     int maxflow() {
131         int ans = 0;
132         while(bfs()) {
133             ans += dfs(s, inf);
134         }
135         return ans;
136     }
137 } dinic;
138 
139 int main()
140 {
141     //freopen("data.txt", "r", stdin);
142     read(n);
143     dinic.init();
144     s = 0, t = 1e5 + 7;
145     int balls = 0, coll = 0;
146     while(coll <= n) {
147         ++balls;
148         dinic.BuildGraph(s, balls * 2, 1);
149         dinic.BuildGraph(balls * 2 + 1, t, 1);
150         for ( int i = sqrt(balls) + 1; i * i < (balls * 2); ++i ) {
151             dinic.BuildGraph((i * i - balls) * 2, balls * 2 + 1, 1);
152         }
153         int maxflow = dinic.maxflow();
154         if(maxflow == 0) {
155             ++coll;
156             Pre[coll] = balls;
157         }
158     }
159     printf("%d\n",balls - 1);
160     for ( int i = 1; i <= n; ++i ) {
161         if(!vis[Pre[i]]) {
162             for ( int u = Pre[i]; u && u != (t / 2); u = Nxt[u] ) {
163                 vis[u] = true;
164                 printf("%d ",u);
165             }
166             puts("");
167         }
168     }
169     return 0;
170 }