【网络流24题】No.4 魔术球问题（二分+最小路径覆盖）

【题意】

　　假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1， 2， 3， ¼的球。
（ 1）每次只能在某根柱子的最上面放球。
（ 2）在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可
放 11 个球。

输入文件示例
input.txt
4

输出文件示例

output.txt

11
1 8
2 7 9
3 6 10
4 5 11

【分析】

　　二分答案。然后连边u->v 表示v可以放在u后面，然后就是一个有向图的最小路径覆盖（点不能重复）

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cmath>
  8 using namespace std;
  9 #define Maxn 4100
 10 #define INF 0xfffffff
 11 
 12 struct node
 13 {
 14     int x,y,f,o,next;
 15 }t[Maxn*1010];int len;
 16 int first[Maxn];
 17 
 18 int mymin(int x,int y) {return x<y?x:y;}
 19 
 20 void ins(int x,int y,int f)
 21 {
 22     t[++len].x=x;t[len].y=y;t[len].f=f;
 23     t[len].next=first[x];first[x]=len;t[len].o=len+1;
 24     t[++len].x=y;t[len].y=x;t[len].f=0;
 25     t[len].next=first[y];first[y]=len;t[len].o=len-1;
 26 }
 27 
 28 int st,ed;
 29 queue<int > q;
 30 int dis[Maxn];
 31 bool bfs()
 32 {
 33     while(!q.empty()) q.pop();
 34     memset(dis,-1,sizeof(dis));
 35     q.push(st);dis[st]=0;
 36     while(!q.empty())
 37     {
 38         int x=q.front();
 39         for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 40         {
 41             int y=t[i].y;
 42             if(dis[y]==-1)
 43             {
 44                 dis[y]=dis[x]+1;
 45                 q.push(y);
 46             }
 47         }
 48         q.pop();
 49     }
 50     if(dis[ed]==-1) return 0;
 51     return 1;
 52 }
 53 
 54 int ffind(int x,int flow)
 55 {
 56     if(x==ed) return flow;
 57     int now=0;
 58     for(int i=first[x];i;i=t[i].next) if(t[i].f>0)
 59     {
 60         int y=t[i].y;
 61         if(dis[y]==dis[x]+1)
 62         {
 63             int a=ffind(y,mymin(flow-now,t[i].f));
 64             t[i].f-=a;
 65             t[t[i].o].f+=a;
 66             now+=a;
 67         }
 68         if(now==flow) break;
 69     }
 70     if(now==0) dis[x]=-1;
 71     return now;
 72 }
 73 
 74 void output()
 75 {
 76     for(int i=1;i<=len;i+=2)
 77      printf("%d->%d %d
",t[i].x,t[i].y,t[i].f);
 78 }
 79 
 80 int max_flow()
 81 {
 82     int ans=0;
 83     while(bfs())
 84     {
 85         ans+=ffind(st,INF);
 86         // printf("--%d
",ans);
 87         // output();
 88     }
 89     return ans;
 90 }
 91 
 92 int n;
 93 bool check(int x)
 94 {
 95     len=0;
 96     memset(first,0,sizeof(first));
 97     for(int i=1;i<=x;i++)
 98      for(int j=i+1;j<=x;j++)
 99      {
100          int yy=i+j,y=(int)sqrt((double)yy);
101          if(y*y==yy)
102          {
103              ins(i,j+x,1);
104          }
105      }
106     st=2*x+1;ed=st+1;
107     for(int i=1;i<=x;i++) ins(st,i,1);
108     for(int i=1;i<=x;i++) ins(i+x,ed,1);
109     // if(x==10) output();
110     int y=max_flow();
111     return x-y<=n;
112 }
113 
114 int nt[Maxn];
115 bool vis[Maxn];
116 
117 int main()
118 {
119     scanf("%d",&n);
120     int l=1,r=2000;
121     while(l<r)
122     {
123         int mid=(l+r+1)>>1;
124         if(check(mid)) l=mid;
125         else r=mid-1;
126     }
127     printf("%d
",l);
128     check(l);
129     // output();
130     memset(nt,0,sizeof(nt));
131     memset(vis,1,sizeof(vis));
132     for(int i=1;i<=len;i+=2) if(t[i].x!=st&&t[i].y!=ed&&t[i].f==0)
133         nt[t[i].x]=t[i].y-l,vis[t[i].y-l]=0;
134     for(int i=1;i<=l;i++) if(vis[i])
135     {
136         int x=i;
137         while(x)
138         {
139             printf("%d ",x);
140             x=nt[x];
141         }
142         printf("
");
143     }
144     return 0;
145 }

View Code

缓慢飘过~~

2016-11-04 10:45:42

【网络流24题】No.4 魔术球问题 （二分+最小路径覆盖）

【网络流24题】No.4 魔术球问题（二分+最小路径覆盖）