bzoj 3158 千钧一发 —— 最小割

时间：2023-11-15 18:17:38

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3158

\( a[i] \) 是奇数则满足条件1，是偶数则显然满足条件2；

因为如果把两个奇数的 \( a[i] \) 写成 \( 2*n+1 \) 和 \( 2*m+1 \)，那么：

\( a[i]^{2} + a[j]^{2} = (2*n+1)^{2} + (2*m+1)^{2} = 4*(n^{2}+n+m^{2}+m) + 2 \)

这是个偶数，所以如果它是完全平方数，那么一定是一个偶数的平方，那么那个 \( +2 \) 就没有办法了，所以它一定不是一个完全平方数；

于是可以把点分成两部分；

然后用最小割的思路，不能一起选就连边，两部分内部的点显然是不互相连边的；

然后原点、汇点分别和两个部分有 \( b[i] \) 的边，跑最小割即可。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

typedef long long ll;

int const xn=,xm=,inf=1e9;

int n,hd[xn],ct=,nxt[xm],to[xm],c[xm],dis[xn],cur[xn],S,T,a[xn],b[xn];

queue<int>q;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}

void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}

bool ck(int a,int b)

{

  ll x=(ll)a*a+(ll)b*b;

  ll t=(ll)sqrt(x);

  return t*t==x;

}

int gcd(int a,int b){return b?gcd(b,a%b):a;};

bool bfs()

{

  for(int i=S;i<=T;i++)dis[i]=;

  dis[S]=; q.push(S);

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hd[x],u;i;i=nxt[i])

    if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);

    }

  return dis[T];

}

int dfs(int x,int fl)

{

  if(x==T)return fl;

  int ret=;

  for(int &i=cur[x],u;i;i=nxt[i])

    {

      if(dis[u=to[i]]!=dis[x]+||!c[i])continue;

      int tmp=dfs(u,min(fl-ret,c[i]));

      if(!tmp)dis[u]=;

      c[i]-=tmp; c[i^]+=tmp;

      ret+=tmp; if(ret==fl)break;

    }

  return ret;

}

int main()

{

  n=rd(); S=; T=n+; int ans=;

  for(int i=;i<=n;i++)a[i]=rd();

  for(int i=;i<=n;i++)b[i]=rd(),ans+=b[i];

  for(int i=;i<=n;i++)

    if(a[i]&)add(S,i,b[i]);

    else add(i,T,b[i]);

  for(int i=;i<=n;i++)

    for(int j=i+;j<=n;j++)

      if(ck(a[i],a[j])&&gcd(a[i],a[j])==)

    {

      if(a[i]&)add(i,j,inf);

      else add(j,i,inf);

    }

  while(bfs())

    {

      memcpy(cur,hd,sizeof hd);

      ans-=dfs(S,inf);

    }

  printf("%d\n",ans);

  return ;

}

相关文章