输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
4
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
11
1 8
2 7 9
3 6 10
4 5 11

 

 

思路

　　既然是网络流24题自然用网络流的思想来建图

　　考虑一个问题，

　　如果把每个柱子考虑成一个特定路径，

　　把柱子上的球看作是路径经过的点号，

　　为了要在固定的路线上经过更多的点，

　　则可以很清晰的知道这是一个最小路径覆盖问题。

　　看出了方向之后自然是思考建图：

　　大家都清楚网络流擅长解决此类有限制条件的线性规划问题。

　　自然要先分析如何把限制条件转化成图上点与点之间的关系上去。

　　首先，先枚举球的个数。竟然没有T

　　把点逐渐加到路径上，

　　因为每个点既要和S连也要和T连，

　　还要和其他点权和为完全平方数的点相连，

　　自然考虑拆点。

　　通过画图容易发现：

　　1、S -> i入, i出 -> T，容量为1

　　2、i入 -> j出

　　当不断加点把图跑满时，再加点不会更新最大流

　　这时就应该引入新的路径，也就是增加柱子个数

　　直到柱子个数 = n

　

CODE

 

  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 }
View Code

 

 

 

#include  < bits/stdc++.h >
#define  dbg( x ) cout  <<  #x  <<  " = "  << x  << endl
#define  eps  1 e - 8
#define  pi  acos( - 1.0 )

using  namespace std ;
typedef  long  long LL ;

const  int inf  =  0x 3f3f3f3f ;

template < class T > inline  void  read(T  & res )
{
     char c ;T flag = 1 ;
     while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

namespace _buff  {
     const  size_t BUFF  =  1  <<  19 ;
     char  ibuf [BUFF ],  *ib  = ibuf ,  *ie  = ibuf ;
     char  getc()  {
         if  (ib  == ie )  {
            ib  = ibuf ;
            ie  = ibuf  +  fread(ibuf ,  1 , BUFF , stdin );
         }
         return ib  == ie  ?  - 1  :  *ib ++ ;
     }
}

int  qread()  {
     using  namespace _buff ;
     int ret  =  0 ;
     bool pos  =  true ;
     char c  =  getc();
     for  (;  (c  <  ' 0 '  || c  >  ' 9 ' )  && c  !=  ' - ' ; c  =  getc())  {
         assert( ~c );
     }
     if  (c  ==  ' - ' )  {
        pos  =  false ;
        c  =  getc();
     }
     for  (; c  >=  ' 0 '  && c  <=  ' 9 ' ; c  =  getc())  {
        ret  =  (ret  <<  3 )  +  (ret  <<  1 )  +  (c  ^  48 );
     }
     return pos  ? ret  :  -ret ;
}

const  int maxn  =  200007 ;

int n , m ;
int s , t ;

struct edge {
     int from ,to ;
    LL cap ,flow ;
};

int  Pre [maxn  <<  1 ],  Nxt [maxn  <<  1 ];
bool  vis [maxn  <<  1 ];

struct DINIC  {
     int  head [maxn  <<  1 ],  nxt [maxn  <<  1 ],  edge [maxn  <<  1 ], cnt ;
     int  cap [maxn  <<  1 ],  depth [maxn  <<  1 ];

     void  init()  {
        cnt  =  1 ;
         memset(head ,  0 ,  sizeof (head ));
     }

     void  BuildGraph( int  u ,  int  v ,  int  w )  {
         ++cnt ;
         edge [cnt ]  = v ;
         nxt [cnt ]  =  head [u ];
         cap [cnt ]  = w ;
         head [u ]  = cnt ;

         ++cnt ;
         edge [cnt ]  = u ;
         nxt [cnt ]  =  head [v ];
         cap [cnt ]  =  0 ;
         head [v ]  = cnt ;
     }

    queue <int> q ;

     bool  bfs()  {
         memset(depth ,  0 ,  sizeof (depth ));
         depth [s ]  =  1 ;
         q .push(s );
         while( ! q .empty())  {
             int u  =  q .front();
             q .pop();
             for  (  int i  =  head [u ]; i ; i  =  nxt [i ]  )  {
                 int v  =  edge [i ];
                 if( depth [v ])  {
                     continue;
                 }
                 if( cap [i ])  {
                     depth [v ]  =  depth [u ]  +  1 ;
                     q .push(v );
                 }
             }
         }
         return  depth [t ];
     }

     int  dfs( int  u ,  int  dist )  {
         if(u  == t )  {
             return dist ;
         }
         int flow  =  0 ;
         for  (  int i  =  head [u ]; i  && dist ; i  =  nxt [i ]  )  {
             if( cap [i ]  ==  0 )
                 continue;
             int v  =  edge [i ];
             if( depth [v ]  !=  depth [u ]  +  1 )  {
                 continue;
             }
             int res  =  dfs(v ,  min( cap [i ], dist ));
             cap [i ]  -= res ;
             cap [i  ^  1 ]  += res ;
            //printf("cap[%d]:%d\n",t, cap[t]);
            dist  -= res ;
            flow  += res ;
             Nxt [u  /  2 ]  = v  /  2 ;
         }
         return flow ;
     }

     int  maxflow()  {
         int ans  =  0 ;
         while(bfs())  {
            ans  +=  dfs(s , inf );
         }
         return ans ;
     }
} dinic ;

int  main()
{
    //freopen("data.txt", "r", stdin);
     read(n );
     dinic .init();
    s  =  0 , t  =  1 e 5  +  7 ;
     int balls  =  0 , coll  =  0 ;
     while(coll  <= n )  {
         ++balls ;
         dinic .BuildGraph(s , balls  *  2 ,  1 );
         dinic .BuildGraph(balls  *  2  +  1 , t ,  1 );
         for  (  int i  =  sqrt(balls )  +  1 ; i  * i  <  (balls  *  2 );  ++i  )  {
             dinic .BuildGraph((i  * i  - balls )  *  2 , balls  *  2  +  1 ,  1 );
         }
         int maxflow  =  dinic .maxflow();
         if(maxflow  ==  0 )  {
             ++coll ;
             Pre [coll ]  = balls ;
         }
     }
     printf( " %d \n " ,balls  -  1 );
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if( ! vis [ Pre [i ]])  {
             for  (  int u  =  Pre [i ]; u  && u  !=  (t  /  2 ); u  =  Nxt [u ]  )  {
                 vis [u ]  =  true ;
                 printf( " %d   " ,u );
             }
             puts( "" );
         }
     }
     return  0 ;
}