「BJOI2012」连连看

题目链接

\(Solution\)

我们首先进行拆点操作，将每个点都拆成\(x\)和\(y\)，将满足条件的两个点连起来就好了(记得要将\(x\)连\(y'\)的同时要将\(y\)联向\(x'\))

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int read(){

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9')

        f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9')

        x=x*10+c-'0',c=getchar();

    return x*f;

}

struct node{

    int to,next,v,w;

}a[1000001];

int dis[10001],f[10001],pre[10001],fa[10001],s,t,n,head[10001],cnt,x,y,z,c;

void add(int x,int y,int c,int v){

    a[++cnt].to=y;

    a[cnt].next=head[x];

    a[cnt].v=c;

    a[cnt].w=v;

    head[x]=cnt;

}

queue < int > q;

int spfa(){

    q.push(s);

    memset(dis,127,sizeof(dis));

    memset(f,0,sizeof(f));

    f[s]=1,dis[s]=0;

    int inf=dis[s+1];

    while(!q.empty()){

        int now=q.front();

        q.pop();

        f[now]=0;

        for(int i=head[now];i;i=a[i].next){

            int v=a[i].to;

            if(dis[v]>dis[now]+a[i].w&&a[i].v){

                dis[v]=dis[now]+a[i].w,pre[v]=i,fa[v]=now;

                if(!f[v])

                    f[v]=1,q.push(v);

            }

        }

    }

    if(dis[t]!=inf)

        return 1;

    return 0;

}

int ans1,ans;

void anser(){

    while(spfa()){

        int minx=2147483647;

        for(int i=t;i!=s;i=fa[i])

            minx=min(minx,a[pre[i]].v);

        ans+=minx,ans1+=dis[t]*minx;

        for(int i=t;i!=s;i=fa[i])

            a[pre[i]].v-=minx,(pre[i]%2)?a[pre[i]+1].v+=minx:a[pre[i]-1].v+=minx;

    }

}

int main(){

    int A=read(),B=read();

    n=B,s=0,t=B+1;

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

        add(s,i,1,0),add(i,s,0,0);

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

        add(i,t,1,0),add(t,i,0,0);

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

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

            int l=i*i-j*j,p=sqrt(l);

            if(p*p==l&&__gcd(j,p)==1){

                add(i,j+B,1,-i-j),add(j+B,i,0,i+j);

				add(j,i+B,1,-i-j),add(i+B,j,0,i+j);

			}

        }

    anser();

    printf("%d %d",ans/2,-1*ans1/2);

}

巴特西

「BJOI2012」连连看

题目链接

\(Solution\)

code

最新文章

热门文章