此题使用了交表。打表的做法参见本博客的另一篇文章《网络流24题》。
以下是我的代码：
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int kMaxn(1350);
const int kMaxm(1000007);
struct Edge
{
int u,v;
};
int ans,nx,ny;
int cnt,first[kMaxn],next[kMaxm];
Edge e[kMaxm];
int maxmatch,cx[kMaxn],cy[kMaxn];
int distx[kMaxn],disty[kMaxn];
int head,tail,q[kMaxn];
void Clear()
{
cnt=0;
for(int i=1;i<=ans;i++)
first[i]=-1;
}
void AddEdge(int u,int v)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
next[cnt]=first[u];
first[u]=cnt;
}
bool OK(int a,int b)
{
return ((int)sqrt((double)a+b))*((int)sqrt((double)a+b))==a+b;
}
void Build()
{
nx=ny=ans;
for(int i=1;i<=ans;i++)
for(int j=i+1;j<=ans;j++)
if(OK(i,j))
AddEdge(i,j);
}
bool BFS()
{
bool re(false);
head=tail=0;
memset(distx,0,sizeof(distx));
memset(disty,0,sizeof(disty));
for(int i=1;i<=nx;i++)
if(cx[i]==-1)
q[tail++]=i;
while(head!=tail)
{
int h,t;
for(h=head,t=tail;h!=t;h=(h+1)%kMaxn)
{
int u(q[h]);
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(!disty[v])
{
disty[v]=distx[u]+1;
if(cy[v]==-1)
re=true;
else
{
distx[cy[v]]=disty[v]+1;
q[tail]=cy[v];
tail=(tail+1)%kMaxn;
}
}
}
}
head=t;
}
return re;
}
bool DFS(int u)
{
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(disty[v]==distx[u]+1)
{
disty[v]=0;
if(cy[v]==-1 || DFS(cy[v]))
{
cx[u]=v;
cy[v]=u;
return true;
}
}
}
return false;
}
void HopcroftKarp()
{
maxmatch=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(BFS())
for(int i=1;i<=nx;i++)
if(cx[i]==-1 && DFS(i))
maxmatch++;
}
int Solve()
{
Clear();
Build();
HopcroftKarp();
return ans-maxmatch;
}
int r[57];
void Init()
{
memset(r,-1,sizeof(r));
for(ans=1;r[50]==-1;ans++)
{
int t(Solve());
if(t>=1 && r[t-1]==-1)
{
r[t-1]=ans-1;
printf("%d\n",r[t-1]);
}
}
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
Init();
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
printf("%d\n",r[n]);
}
}
posted on 2011-08-27 10:43
lee1r 阅读(380)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论