bzoj 2661: [BeiJing wc2012]连连看

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define M 10000
#define inf 2139062143
using namespace std;
int cnt=,n,m,T,d[M],q[*M],f[M],head[M],next[*M],u[*M],v[*M],w[*M],fro[*M],fr[M];
int ans,sum;
void jia1(int a1,int a2,int a3,int a4)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
fro[cnt]=a1;
u[cnt]=a2;
v[cnt]=a3;
w[cnt]=a4;
}
void jia(int a1,int a2,int a3,int a4)
{
jia1(a1,a2,a3,a4);
jia1(a2,a1,,-a4);
return;
}
bool spfa()
{
memset(d,,sizeof(int)*(T+));
d[]=;
f[]=;
q[]=;
int h=,t=;
for(;h<t;)
{
h++;
int p=q[h];
f[p]=;
for(int i=head[p];i;i=next[i])
if(v[i]&&d[u[i]]>d[p]+w[i])
{
d[u[i]]=d[p]+w[i];
fr[u[i]]=i;
if(!f[u[i]])
{
f[u[i]]=;
t++;
q[t]=u[i];
}
}
}
if(d[T]!=inf)
return ;
return ;
}
void mcf()
{
int mx=inf;
for(int i=fr[T];i;i=fr[fro[i]])
mx=min(mx,v[i]);
for(int i=fr[T];i;i=fr[fro[i]])
{
v[i]-=mx;
v[i^]+=mx;
ans+=mx*w[i];
}
sum+=mx;
return;
}
int gcd(int a1,int a2)
{
int a3=a1%a2;
for(;a3;)
{
a1=a2;
a2=a3;
a3=a1%a2;
}
return a2;
}
int main()
{
scanf("%d%d",&n,&m);
T=;
for(int i=n;i<=m;i++)
{
jia(,i,,);
jia(i+,T,,);
}
for(int i=n;i<=m;i++)
for(int j=n;j<i;j++)
{
double a1=sqrt(i*i-j*j);
int a2=floor(a1);
if(a2==a1&&gcd(a2,j)==)
{
jia(i,j+,,-i-j);
jia(j,i+,,-i-j);
}
}
for(;spfa();)
mcf();
printf("%d %d\n",sum/,-ans/);
return ;
}

网络流如果满足条件,x向y‘连费用为z的边,y向x’连费用为z的边,最后除2便是答案。

上一篇:Java利用httpasyncclient进行异步HTTP请求


下一篇:java实现的集中排序算法