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

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






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;
        int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0;
        for(int i=h[u];~i;i=n1[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;
    }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++)
    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;    
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