「网络流24题」魔术球问题
Description
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
编程任务：
对于给定的n，计算在n根柱子上最多能放多少个球。
Input Format
文件第1 行有1个正整数n，表示柱子数。
Output Format
程序运行结束时，将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。
Sample Input
|
1 |
4 |
Sample Output
|
1 2 3 4 5 |
11 1 8 2 7 9 3 6 10 4 5 11 |
题解
枚举答案A，在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数，连接一条有向边(i,j)。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于N，那么A是一个可行解，在所有可行解中找到最大的A，即为最优解。
具体方法可以顺序枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解。
换了一种得出方案的方法
|
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 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #define T 10000 #define inf 0x7fffffff using namespace std; int n,cnt=1,ans,s,head[10001],q[10001],to[10001],h[10001]; bool mark[10001]; struct data{int to,next,v;}e[200001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} bool bfs() { int t=0,w=1,i,now; memset(h,-1,sizeof(h)); h[0]=q[0]=0; while(t<w) { now=q[t];t++; i=head[now]; while(i) { if(h[e[i].to]==-1&&e[i].v) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;} i=e[i].next; } } if(h[T]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==T)return f; int i=head[x]; int w,used=0; while(i) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w; e[i^1].v+=w; used+=w; if(used==f)return f; } i=e[i].next; } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())ans-=dfs(0,inf);} int main() { scanf("%d",&n); while(1) { ans++;s++; for(int i=1;i<s;i++) if(sqrt(i+s)==(int)(sqrt(i+s))) insert(i,s+5000,1); insert(0,s,1);insert(s+5000,T,1); dinic(); if(ans>n)break; } printf("%d\n",s-1); for(int i=1;i<s;i++) { int k=head[i]; while(k) { if(!e[k].v){to[i]=e[k].to-5000;break;} k=e[k].next; } } for(int i=1;i<s;i++) { if(mark[i])continue;int t=i; while(t!=-5000) { mark[t]=1; printf("%d ",t); t=to[t]; } printf("\n"); } return 0; } |
计数器 9854172
OI 课件=>
OI 课件=>
问下黄学长有网络流24题里面要输出方案的这些题的spj吗，或者说在哪儿能测到有spj的？
….这程序不是wa的吗
很多地方测试没有spj吧
噢，原来第一个数可以随便放，傻逼了。。hh