3158: 千钧一发

题目：传送门

题解：

　　这是一道很好的题啊...极力推荐

　　细看题目：要求一个最大价值，那么我们可以转换成求损失的价值最小

　　那很明显就是最小割的经典题目啊？！

　　但是这里两个子集的分化并不明显...GG

　　耐心一点，从题目的要求再入手：

　　对于第二个要求，如果两点的a值都为偶数，那么肯定满足

　　那如果两个数都为奇数的话，也必定满足要求一，证明如下：

　　 1、一个奇数的平方%4为1，一个偶数的平方%4为0

　　 2、两个奇数的平方和%4为2

　　 3、如果两个奇数的平方和是一个奇数的平方，那么%4应该为1，不符合

　　 4、如果两个奇数的平方和是一个偶数的平方，那么%4应该为0，不符合

　　因此得证。

　　这样子思考的话，两个子集的分化就较为明显了：

　　 st向a值为奇数的相连，a值为偶数的向ed相连，容量都为b值；这样子所形成的两个子集里面的点一定都是符合要求的。

　　最后一步，也是最关键的一步：

　　两个子集之间两两匹配，如果当前匹配的两个点是不符合要求的，就将这两个点相连，容量为无限大。

　　有什么用呢？自己画几个图便很容易理解：

　　这时候我们跑最小割的话，割出来的边就是损失价值的最小值

　　用sum-最小割就是答案啊

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define qread(x) x=read()

 using namespace std;

 typedef long long LL;

 const LL inf=;

 LL n,st,ed,sum;

 LL A[],B[];

 inline LL read()

 {

     LL f=,x=;char ch;

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

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return f*x;

 }

 struct node

 {

     LL x,y,c,next,other;

 }a[];LL len,last[];

 void ins(LL x,LL y,LL c)

 {

     int k1,k2;

     k1=++len;

     a[len].x=x;a[len].y=y;a[len].c=c;

     a[len].next=last[x];last[x]=len;

     k2=++len;

     a[len].x=y;a[len].y=x;a[len].c=;

     a[len].next=last[y];last[y]=len;

     a[k1].other=k2;

     a[k2].other=k1;

 }

 LL list[],h[],head,tail;

 bool bt_h()

 {

     memset(h,,sizeof(h));h[st]=;

     list[]=st;head=;tail=;

     while(head!=tail)

     {

         int x=list[head];

         for(int k=last[x];k;k=a[k].next)

         {

             int y=a[k].y;

             if(h[y]== && a[k].c)

             {

                 h[y]=h[x]+;

                 list[tail++]=y;

             }

         }

         head++;

     }

     if(h[ed])return true;

     return false;

 }

 LL find_flow(LL x,LL flow)

 {

     if(x==ed)return flow;

     LL s=,t;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(h[y]==h[x]+ && a[k].c> && flow>s)

         {

             s+=t=find_flow(y,min(a[k].c,flow-s));

             a[k].c-=t;a[a[k].other].c+=t;

         }

     }

     if(s==)h[x]=;

     return s;

 }

 LL gcd(LL a,LL b)

 {

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

 }

 bool pd(LL x,LL y)

 {

     LL T=x*x+y*y,t=sqrt(T);

     if(t*t!=T)return true;

     if(gcd(x,y)>)return true;

     return false;

 }

 int main()

 {

     sum=;

     qread(n);

     len=;memset(last,,sizeof(last));

     for(int i=;i<=n;i++)qread(A[i]);

     for(int i=;i<=n;i++){qread(B[i]);sum+=B[i];}

     st=n+;ed=st+;

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

     {

         if(A[i]%==)ins(st,i,B[i]);

         else ins(i,ed,B[i]);

     }

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

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

             if((A[i]%==) && (A[j]%==) && !pd(A[i],A[j]))

                 ins(i,j,inf);

     LL ans=;

     while(bt_h())ans+=find_flow(st,inf);

     printf("%lld\n",sum-ans);

     return ;

 }

巴特西

bzoj3158&3275: 千钧一发（最小割）

3158: 千钧一发

最新文章

热门文章