LOJ6003 - 「网络流 24 题」魔术球

原题链接

Description

假设有n(n≤55)根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,4,⋯的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何2个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在n根柱子上最多能放多少个球。

Solution

如果u+v(u<v)是完全平方数则连有向边(u,v),那么一个柱子上的球就相当于图中的一条路径。二分答案,以是否能用不超过n条路径覆盖作为条件。

Code

//「网络流 24 题」魔术球
#include <cstdio>
#include <cstring>
int const N=1e4+10;
int n,ans[100]={0,1,3,7,11,17,23,31,39,49,59,71,83,97,111,127,143,161,179,199,219,241,263,287,311,337,363,391,419,449,479,511,543,577,611,647,683,721,759,799,839,881,923,967,1011,1057,1103,1151,1199,1249,1299,1351,1403,1457,1511,1567};
int cnt,h[N];
struct edge{int v,nxt;} ed[N*100];
void edAdd(int u,int v) {cnt++; ed[cnt].v=v,ed[cnt].nxt=h[u],h[u]=cnt;}
int link[N]; bool used[N];
int find(int u,int lim)
{
for(int i=h[u];i;i=ed[i].nxt)
{
int v=ed[i].v;
if(used[v]||v>lim) continue;
used[v]=true;
if(!link[v]||find(link[v],lim)) {link[v]=u; return true;}
}
return false;
}
int Hungrian(int lim)
{
int ans=0; memset(link,0,sizeof link);
for(int i=1;i<=lim;i++)
{
memset(used,0,sizeof used);
if(find(i,lim)) ans++;
}
return ans;
}
int pre[N],nxt[N];
int main()
{
scanf("%d",&n);
cnt=0; memset(h,0,sizeof h);
for(int i=1;i<=n;i++)
for(int u=1;u<i*i-u;u++) edAdd(u,i*i-u);
Hungrian(ans[n]);
printf("%d\n",ans[n]);
for(int i=1;i<=ans[n];i++) pre[i]=link[i],nxt[link[i]]=i;
for(int i=1;i<=ans[n];i++)
{
if(pre[i]) continue;
for(int u=i;u;u=nxt[u]) printf("%d ",u);
printf("\n");
}
return 0;
}

P.S.

比较有毒的是本机TLE但交上去很快…速度大概差十倍吧。我为了不T还打了表= = hzwer的源码本机2s+交上去115ms

上一篇:Nginx+Tomcat+Memcached实现会话保持


下一篇:转:ibatis的cacheModel