2017-03-17 18:45:01

#include <stdio.h>
#include <cstring>
#include <queue>
#include <cmath>
#define maxn 100001
#define E 40000
#define mid 5001
#define fill(x,y) memset(x,y,sizeof(x))
#define min(x,y) x<y?x:y
#define INF 0x7f7f7f7f
using namespace std;
struct edge{int y,w,rev,next;}e[maxn];
int ls[maxn],n,m,maxE=0,vis[maxn],state[maxn];
{
e[++maxE]=(edge){y,w,maxE+1,ls[x]};
ls[x]=maxE;
e[++maxE]=(edge){x,0,maxE-1,ls[y]};
ls[y]=maxE;
}
int bfs(int x)
{
queue <int> t;
t.push(x);
fill(state,63);
state[x]=0;
while (!t.empty())
{
int tt=t.front();t.pop();
for (int i=ls[tt];i;i=e[i].next)
{
if (e[i].w>0&&state[tt]+1<state[e[i].y])
{
state[e[i].y]=state[tt]+1;
t.push(e[i].y);
if (e[i].y==E)
return true;
}
}
}
return false;
}
int find(int x,int mn)//dinic
{
if (x==E) return mn;
for (int i=ls[x];i;i=e[i].next)
if (state[x]+1==state[e[i].y]&&e[i].w>0)
{
int d=find(e[i].y,min(mn,e[i].w));
if (d>0)
{
e[i].w-=d;
e[e[i].rev].w+=d;
vis[x]=e[i].y;
return d;
}
}
return 0;
}
int main()
{
int n;
scanf("%d",&n);
int t=0,ans=0;
while (1)//从小到大枚举答案
{
t++;
for (int i=1;i<t;i++)
if (sqrt(t+i)==(int)sqrt(t+i))
if (bfs(0))//跑最小路径覆盖
ans+=find(0,INF);
if (t-ans>n)//如果最小路径覆盖大于柱子数就退出
{
ans=t-1;
break;
}
}
fill(ls,0);
fill(vis,0);
maxE=0;
for (int i=1;i<=ans;i++)
for (int j=1;j<=ans;j++)
for (int i=1;i<=j-1;i++)
if (sqrt(i+j)==(int)sqrt(i+j))
int l=0;
while (bfs(0))//在跑一边求出路径
l+=find(0,INF);
printf("%d\n",ans);
for (int i=1;i<=ans;i++)//输出路径
{
if (vis[i]!=0)
{
int t=i;
do
{
if (t>mid) t-=mid;
printf("%d ",t);
int x=vis[t];
vis[t]=0;
t=x;
}
while (t!=0);
printf("\n");
}
}
}
• star
首页