【费用流】bzoj2661 [BeiJing wc2012]连连看

时间：2023-12-04 12:25:50

将每个数拆点，互相连边，然后满足条件的数对之间互相连边，跑最大费用流，答案是流量和费用分别除以2。

一定要i->j、j->i都连上，否则可能会出现一个数在一边被选择了，在另一边的另一个匹配中又被选择的情况。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

#define MAXN 2002

#define MAXM 500001

#define INF 2147483647

int S,T,n,A,B;

int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array

bool inq[MAXN];

int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;

queue<int>q;

void Init_MCMF(){memset(first,-1,sizeof(first));en=0;S=0;T=(B<<1|1);}

void AddEdge(const int &U,const int &V,const int &W,const int &C)

{u[en]=U; v[en]=V; cap[en]=W; cost[en]=C; next[en]=first[U]; first[U]=en++;

u[en]=V; v[en]=U; cost[en]=-C; next[en]=first[V]; first[V]=en++;}

bool Spfa(int &Flow,int &Cost)

{

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

    memset(inq,0,sizeof(inq));

    d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);

    while(!q.empty())

      {

        int U=q.front(); q.pop(); inq[U]=0;

        for(int i=first[U];i!=-1;i=next[i])

          if(cap[i] && d[v[i]]>d[U]+cost[i])

            {

              d[v[i]]=d[U]+cost[i];

              p[v[i]]=i;

              a[v[i]]=min(a[U],cap[i]);

              if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}

            }

      }

    if(d[T]>2100000000) return 0;

    Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;

    while(U!=S)

      {

        cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];

        U=u[p[U]];

      }

    return 1;

}

int Mincost()

{

    int Flow=0,Cost=0;

    while(Spfa(Flow,Cost));

    printf("%d %d\n",Flow>>1,(-Cost)>>1);

}

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

int sqr(const int &x){return x*x;}

bool check(const int &a,const int &b)

{

	int t=a*a-b*b;

	if(sqr((int)sqrt(t))!=t) return 0;

	if(gcd(b,(int)sqrt(t))==1) return 1;

	return 0;

}

int main()

{

	scanf("%d%d",&A,&B); Init_MCMF();

	for(int i=A;i<=B;++i)

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

	    if(check(i,j))

	      {

	      	AddEdge(i,j+B,1,-i-j);

	        AddEdge(j,i+B,1,-i-j);

		  }

	for(int i=A;i<=B;++i)

	  {

	  	AddEdge(S,i,1,0);

	  	AddEdge(i+B,T,1,0);

	  }

	Mincost();

	return 0;

}

　　

相关文章