【BZOJ3158】千钧一发 最小割

【BZOJ3158】千钧一发

Description

Input

第一行一个正整数N。

第二行共包括N个正整数，第 个正整数表示Ai。

第三行共包括N个正整数，第 个正整数表示Bi。

Output

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

Sample Input

4
3 4 5 12
9 8 30 9

Sample Output

39

题解：一开始直接把Number那道题粘了下来交上去，结果发现并不一样~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#include <algorithm>

#include <cmath>

using namespace std;

int n,cnt,tot,ans,tx,ty;

typedef long long ll;

queue<int> q;

int A[1010],B[1010];

int vx[1010],vy[1010],ex[1010],ey[1010],next[2000000],head[6010],to[2000000],val[2000000],d[6010];

int gcd(int a,int b)

{

	return (b==0)?a:gcd(b,a%b);

}

int dfs(int x,int mf)

{

	if(x==n+1)	return mf;

	int i,k,temp=mf;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(d[to[i]]==d[x]+1&&val[i])

		{

			k=dfs(to[i],min(temp,val[i]));

			if(!k)	d[to[i]]=0;

			val[i]-=k,val[i^1]+=k,temp-=k;

			if(!temp)	break;

		}

	}

	return mf-temp;

}

int bfs()

{

	int i,u;

	memset(d,0,sizeof(d));

	while(!q.empty())	q.pop();

	q.push(0),d[0]=1;

	while(!q.empty())

	{

		u=q.front(),q.pop();

		for(i=head[u];i!=-1;i=next[i])

		{

			if(!d[to[i]]&&val[i])

			{

				d[to[i]]=d[u]+1;

				if(to[i]==n+1)	return 1;

				q.push(to[i]);

			}

		}

	}

	return 0;

}

void add(int a,int b,int c)

{

	to[cnt]=b;

	val[cnt]=c;

	next[cnt]=head[a];

	head[a]=cnt++;

}

int main()

{

	scanf("%d",&n);

	int i,j,k,k1;

	memset(head,-1,sizeof(head));

	for(i=1;i<=n;i++)	scanf("%d",&A[i]);

	for(i=1;i<=n;i++)	scanf("%d",&B[i]),tot+=B[i];

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

	{

		if(A[i]&1)	add(0,i,B[i]),add(i,0,0);

		else	add(i,n+1,B[i]),add(n+1,i,0);

	}

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

	{

		for(j=1;j<=n;j++)

		{

			if(!(A[i]&1)||(A[j]&1)||gcd(A[i],A[j])>1)	continue;

			ll k=(ll)A[i]*A[i]+(ll)A[j]*A[j];

			if(ll(sqrt(k))*ll(sqrt(k))==k)

			{

				add(i,j,1<<30);

				add(j,i,0);

			}

		}

	}

	while(bfs())	ans+=dfs(0,1<<30);

	printf("%d",tot-ans);

	return 0;

}