1 条题解

  • 0
    @ 2022-8-9 19:40:57
    
    
    #include<bits/stdc++.h>
    using namespace std;
    struct edge{int x,y,c,pre,other;}a[1110000];int alen,last[410],h[410],st,ed;
    void ins(int x,int y,int c){
    a[++alen]=edge{x,y,c,last[x],alen+1};last[x]=alen;
    a[++alen]=edge{y,x,0,last[y],alen-1};last[y]=alen;
    }
    bool bh(){
    memset(h,0,sizeof(h));h[st]=1;
    queue<int>Q;Q.push(st);
    while(!Q.empty()){
    int x=Q.front();
    for(int k=last[x];k>0;k=a[k].pre){
    int y=a[k].y;
    if(h[y]==0&&a[k].c>0){
    h[y]=h[x]+1;
    Q.push(y);
    }
    }
    Q.pop();
    }
    return h[ed]>0;
    }
    int findflow(int x,int f){
    if(x==ed)return f;
    int sx=0;
    for(int k=last[x];k>0;k=a[k].pre){
    int y=a[k].y;
    if(a[k].c>0&&f-sx&&h[y]==(h[x]+1)){
    int sy=findflow(y,min(a[k].c,f-sx));
    a[k].c-=sy;a[a[k].other].c+=sy;
    sx=sx+sy;
    }
    }
    if(sx==0)h[x]=0;
    return sx;
    }
    int main(){
    int n,p,q;scanf("%d%d%d",&n,&p,&q);
    alen=0;memset(last,0,sizeof(last));
    st=p+q+2*n+1;ed=st+1;
    for(int i=1;i<=p;i++)ins(st,i,1);
    for(int i=1;i<=q;i++)ins(p+2*n+i,ed,1);
    for(int i=1;i<=n;i++)ins(p+i,p+n+i,1);
    for(int i=1;i<=n;i++){
    for(int j=1;j<=p;j++){
    int x;
    scanf("%d",&x);
    if(x==1){
    ins(j,i+p,1);
    }
    }
    }
    for(int i=1;i<=n;i++){
    for(int j=1;j<=q;j++){
    int x;
    scanf("%d",&x);
    if(x==1){
    ins(i+n+p,j+n*2+p,1);
    }
    }
    }
    int ans=0;while(bh())ans+=findflow(st,0x3fffffff);
    printf("%d",ans);
    return 0;
    }
    
    
    • 1

    信息

    ID
    402
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    2
    已通过
    2
    上传者