BZOJ2661: [BeiJing wc2012]连连看【费用流】

dzy posted @ 2013年6月10日 21:13 in BZOJ with tags BZOJ 二分图 费用流 , 1626 阅读

二分图。赤果果的费用流。其实是KM。但是不会写。只好写费用流替代了。

先O(n^2)判哪些数对(x,y)可行。然后连边,做最大费用流。

因为每个数只能取一次。那么我把(x,y)和(y,x)都连了一遍。那么结果除以二。

判断选了几对,只要看T点的流量有多少不是从TT流过来的就行了。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm=5000000,inf=1061109567;
int h[10005],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[10005],inq[10005];
int sq[1000005]={0},S,T,TT,An=0,path[maxm],pre[10005],tot=0;
inline void ae(int a,int b,int cc,int co){
    p[tot]=b; c[tot]=cc; cost[tot]=co;  n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; c[tot]=0;  cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++;
}inline int spfa(){
    memset(sp,63,sizeof(sp));   memset(inq,0,sizeof(inq));
    int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1;
    while(head!=tail){
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){
                path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i];
                if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;}
            }
    }return sp[T]!=inf;
}inline int aug(){
    int delta=inf,  flow=0;
    for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]);
    for(int i=T;pre[i]!=-1;i=pre[i]){
        c[path[i]]-=delta, c[path[i]^1]+=delta;
        flow+=cost[path[i]]*delta;
    }return flow;
}inline int cf(){
    int ret=0; while(spfa()) ret+=aug(); return ret;
}int gcd(int a,int b){
    return (!b)?a:gcd(b,a%b);
}int main(){
    int a,b;    scanf("%d%d",&a,&b);    memset(h,-1,sizeof(h));
    for(int i=1;i<=1000;i++) sq[i*i]=i; S=0;TT=(b-a+1)<<1|1;T=TT+1;
    for(int i=a;i<=b;i++) for(int j=i+1;j<=b;j++)
        if(sq[j*j-i*i]&&gcd(sq[j*j-i*i],i)==1){
            ae(j-a+1,b-a+1+i-a+1,1,-i-j);
            ae(i-a+1,b-a+1+j-a+1,1,-i-j);
        }ae(TT,T,inf,0);
    for(int i=1;i<=b-a+1;i++) ae(S,i,1,0), ae(i,TT,1,0), ae(b-a+1+i,T,1,0);
    int An1,An2=-cf();
    for(int i=h[T];~i;i=n1[i]) if(p[i]==TT)An=b-a+1-c[i];
    printf("%d %d\n",An>>1,An2>>1);  return 0;    
}
Avatar_small
Emma 说:
2023年1月24日 22:11

This problem from the Beijing WC2012 requires a clever approach to solve it. The solution is to firstly solve the cost flow problem with O(n^2) complexity, then connect real estate property management Chatsworth both sides and get the maximum cost flow. The flow is then divided by two to ensure that each number can only be taken once. To check how many pairs are selected, simply look at how much of the traffic at point T does not flow from TT. This is an interesting and creative solution to a complex problem.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter