计产生在n根柱子上极度多能扩多少只球。计算在n根柱子上无限多克推广小只球。

2014年3月7日3,5344

Description 

借用设有n根柱子,现要以下述规则以即时n根柱子中相继放入编号为1,2,3,…的球。
(1)每次只能当某根柱子的无比上面放球。
(2)在同等根柱子中,任何2只相互邻球的号子的与为完全平方数。
试设计一个算法,计算起当n根柱子上最为多会推广多少只球。例如,在4
根柱上顶多但 放11 独球。 编程任务:
对于给定的n,计算以n根柱子上极其多能扩多少只圆球。

Description

假设有n根柱子,现要按照下述规则以马上n根柱子中相继放入编号为1,2,3,4底圆球。
(1)每次只能当某根柱子的无比上面放球。
(2)在同等根柱中,任何2只相互邻球的数码的同为全平方数。
尝试设计一个算法,计算起当n根柱子上无比多克加大多少只球。例如,在4
根柱上无与伦比多但放大11 单球。

编程任务:
于给定的n,计算在n根柱子上顶多会加大小只球。

Input 

是因为文件input.txt提供输入数据。文件第1
行有1独正整数n(n<=55),表示柱子数。

Input Format

文件第1 行有1只刚整数n,表示柱子数。

Output 

程序运行结束时,将n 根柱子上最多克加大之球数以及相应的停方案输出及文件
output.txt中。文件之率先实行是球数。接下来的n行,每行是同一清柱上之球体的号。

Sample Input

4

Sample Output

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

 

题解:

其次分叉太深球数。

因而当下几乎单球来举行顶小路径覆盖

能满足加起来相当于平方数的就连边(注意
i<j).

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 using namespace std;
  7 const int N=5005,INF=1999999999;
  8 int gi(){
  9     int str=0;char ch=getchar();
 10     while(ch>'9' || ch<'0')ch=getchar();
 11     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
 12     return str;
 13 }
 14 int k,head[N],num=1,S=0,T;
 15 struct Lin{
 16     int next,to,dis;
 17 }a[N*10];
 18 void init(int x,int y,int dis){
 19     a[++num].next=head[x];
 20     a[num].to=y;
 21     a[num].dis=dis;
 22     head[x]=num;
 23     a[++num].next=head[y];
 24     a[num].to=x;
 25     a[num].dis=0;
 26     head[y]=num;
 27 }
 28 bool pd(int x,int y){
 29     int tmp=sqrt(x+y);
 30     if(tmp*tmp==x+y)return true;
 31     return false;
 32 }
 33 int q[N],dep[N];
 34 bool bfs()
 35 {
 36     memset(dep,0,sizeof(dep));
 37     int t=0,sum=1,u,x;
 38     q[1]=S;dep[S]=1;
 39     while(t!=sum)
 40     {
 41         x=q[++t];
 42         for(int i=head[x];i;i=a[i].next){
 43             u=a[i].to;
 44             if(a[i].dis<=0 || dep[u])continue;
 45             dep[u]=dep[x]+1;q[++sum]=u;
 46         }
 47     }
 48     return dep[T];
 49 }
 50 int dfs(int x,int flow)
 51 {
 52     if(x==T || !flow)return flow;
 53     int u,tmp,tot=0;
 54     for(int i=head[x];i;i=a[i].next){
 55         u=a[i].to;
 56         if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue;
 57         tmp=dfs(u,min(flow,a[i].dis));
 58         a[i].dis-=tmp;a[i^1].dis+=tmp;
 59         tot+=tmp;flow-=tmp;
 60         if(!flow)break;
 61     }
 62     return tot;
 63 }
 64 int maxflow()
 65 {
 66     int tot=0,tmp;
 67     while(bfs()){
 68         tmp=dfs(S,INF);
 69         while(tmp)tot+=tmp,tmp=dfs(S,INF);
 70     }
 71     return tot;
 72 }
 73 void Clear(){
 74     memset(head,0,sizeof(head));
 75     num=1;
 76 }
 77 bool check(int n)
 78 {
 79     T=(n<<1)+1;
 80     for(int i=1;i<=n;i++)init(S,i,1),init(i+n,T,1);
 81     for(int i=1;i<=n;i++)
 82     for(int j=i+1;j<=n;j++){
 83         if(pd(i,j))
 84         init(i,j+n,INF);
 85     }
 86     int tp=n-maxflow();
 87     return tp<=k;
 88 }
 89 bool vis[N];int ans=0;
 90 void putans(int x)
 91 {
 92     printf("%d ",x);
 93     vis[x]=true;
 94     for(int i=head[x];i;i=a[i].next){
 95         if(a[i].dis==INF-1)putans(a[i].to-ans);
 96     }
 97 }
 98 int main()
 99 {
100     k=gi();int l=k,r=2000,mid;
101     while(l<=r){
102         mid=(l+r)>>1;
103         if(check(mid))ans=mid,l=mid+1;
104         else r=mid-1;
105         Clear();
106     }
107     check(ans);
108     printf("%d\n",ans);
109     for(int i=1;i<=ans;i++){
110         if(vis[i])continue;
111         putans(i); 
112         printf("\n");
113     }
114     return 0;
115 }

 

Output Format

程序运行结束时,将n
根柱子上极多会放开之球数以及对应的停放方案输出。文件的首先执行是球数。接下来的n行,每行是同样干净柱子上之圆球的号码。

Sample Inpu

 4

Sample Output

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

 

题解:这道题就是小之要以好的下边,所以保证了DAG的属性。

倘若a,b(a<b)并且a+b是一个平方数。

那a–>b连一长长的边,那么问题是休是转发为,一个DAG最少要多少条路径(不思量交),可以

毕盖,如果跨越了n则不行。

所以保护一下网络流,codevs上没开spj,路径方面处理一下。

 

  1 #include<cstring>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<iostream>
  6 #include<queue>
  7 
  8 #define N 10007
  9 #define M 200007
 10 #define INF 1000000007
 11 using namespace std;
 12 inline int read()
 13 {
 14     int x=0,f=1;char ch=getchar();
 15     while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
 16     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 17     return x*f;
 18 }
 19 
 20 int n,S,T,ans,s;
 21 int cnt=1,head[N],rea[M],val[M],next[M];
 22 int dis[N],to[N],flag[N];
 23 
 24 void add(int u,int v,int fee)
 25 {
 26     next[++cnt]=head[u];
 27     head[u]=cnt;
 28     rea[cnt]=v;
 29     val[cnt]=fee;
 30 }
 31 bool bfs()
 32 {
 33     for (int i=1;i<=T;i++)dis[i]=0;
 34     dis[S]=1;queue<int>q;q.push(S);
 35     while(!q.empty())
 36     {
 37         int u=q.front();q.pop();
 38         for (int i=head[u];i!=-1;i=next[i])
 39         {
 40             int v=rea[i],fee=val[i];
 41             if (!dis[v]&&fee>0)
 42             {
 43                 dis[v]=dis[u]+1;
 44                 if (v==T) return 1;
 45                 q.push(v);
 46             }
 47         }
 48     }
 49     return 0;
 50 }
 51 int dfs(int u,int MF)
 52 {
 53     int res=0;
 54     if (u==T||MF==0) return MF;
 55     for (int i=head[u];i!=-1;i=next[i])
 56     {
 57         int v=rea[i],fee=val[i];
 58         if (dis[v]!=dis[u]+1) continue;
 59         int x=dfs(v,min(MF,fee));
 60         if (x)
 61         {
 62             val[i]-=x,val[i^1]+=x;
 63             MF-=x,res+=x;
 64             if (MF==0) return res;
 65         }
 66     }
 67     if (!res) dis[u]=0;
 68     return res;
 69 }
 70 void Dinic()
 71 {
 72     int res=0;
 73     while(bfs())
 74     {
 75         int x=dfs(S,INF);
 76         while(x)
 77         {
 78             res+=x;
 79             x=dfs(S,INF);
 80         }
 81     }
 82     ans-=res;
 83 }
 84 int main()
 85 {
 86     memset(head,-1,sizeof(head));
 87     n=read();
 88     S=0,T=10001;
 89     while(true)
 90     {
 91         ans++,s++;
 92         for (int i=1;i<s;i++)
 93             if (sqrt(i+s)==(int)(sqrt(i+s))) add(i,s+5000,1),add(s+5000,i,0);
 94         add(S,s,1),add(s,S,0),add(s+5000,T,1),add(T,s+5000,0);
 95         Dinic();
 96         if (ans>n) break;    
 97     }
 98     printf("%d\n",s-1);
 99     for (int i=1;i<s;i++)
100         for (int j=head[i];j!=-1;j=next[j])
101         {
102             int v=rea[j],fee=val[j];
103             if (!fee) {to[i]=v-5000;break;}
104         }
105     for (int i=1;i<s;i++)
106     {
107         if (flag[i]) continue;
108         int t=i;
109         while(t!=-5000)
110         {
111             flag[t]=1;
112             printf("%d ",t);
113             t=to[t];
114         }
115         printf("\n");
116     }//十分巧妙的构思,转化问题十分优秀。 
117 }

 

 

相关文章