题解 P4134 【[BJOI2012]连连看】

题解- P4134 连连看

题目大意

就是在 $[a,b]$ 区间中找出尽量多的数对 $(x,y)$ ,若两种情况下数对数相同使得若干对数对和尽量大。

$Sol$

这道题目难点在于如何转换到熟悉的模型——最小费用最大流。但是题目要我们求数对和尽量大，所以我们只要把边权取反相当于求最小费用，最后答案再去一遍反即可。因为这样我们就可以用简单的方法来解决这道题目了。

于是就很简单：

对于一个成立的数对 $(x,y)$ 从 $x$ 到 $y+b$ 连一条费用为 $-x-y$ 的边流量为 $1$ 的边即可。

从超级源点向 $[a,b]$ 连边权为 $0$ 流量为 $1$ 的边，从 $[a,b]$ 连边权为 $0$ 流量为 $1$ 的边向超级汇点。

$Code$

#include <bits/stdc++.h>
using namespace std;

const int N=2005;
const int M=2e5+5;

int n,m,cnt=1,ans1,ans2,s,t;
int head[N],lb[M],ld[N];
int dis[N],vis[N],fl[M];
struct nood {
    int fr,nex,to,w,fl;
};
nood e[M<<2];

inline void jia(int u,int v,int w,int fl) {
    e[++cnt].nex=head[u];
    e[cnt].fr=u; 
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].fl=fl;
}

inline int gcd(int a,int b) {
    if(!b) return a;
    return gcd(b,a%b);
}

inline bool spfa() {
    queue<int> q;
    memset(dis,63,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(fl,63,sizeof(fl));
    q.push(s),dis[s]=0,vis[s]=1,ld[t]=-1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for ( int i=head[u];i;i=e[i].nex ) {
            int v=e[i].to;
            if(e[i].fl&&dis[v]>dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                fl[v]=min(fl[u],e[i].fl);
                ld[v]=u;
                lb[v]=i;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return (ld[t]!=-1);
}

inline void dinic() {
    while(spfa()) {
        int u=t;
        ans1+=fl[t];
        ans2+=fl[t]*dis[t];
        while(s!=u) {
            e[lb[u]].fl-=fl[t];
            e[lb[u]^1].fl+=fl[t];
            u=ld[u];
        }
    }
    ans1/=2;
    printf("%d %d\n",ans1,-1*ans2/2);
    exit(0);
}

int main() {
    scanf("%d%d",&n,&m);
    s=n-1,t=n+m+1;
    for ( int i=n;i<=m;i++ ) {
        jia(s,i,0,1),jia(i,s,0,0);
        jia(i+m,t,0,1),jia(t,i+m,0,0);
    }
    for ( int i=n;i<=m;i++ ) 
        for ( int j=n;j<i;j++ ) {
            int o=i*i-j*j;
            if((int)sqrt(o)*(int)sqrt(o)==o) {
                int rua=sqrt(o);
                if(gcd(rua,j)==1) { 
                    jia(i,j+m,-i-j,1),jia(j+m,i,i+j,0);
                    jia(j,i+m,-i-j,1),jia(i+m,j,i+j,0);
                }
            }
        }
    dinic();
    return 0;
}