[Wf2011]Chips Challenge

两个条件都不太好处理

每行放置的个数实际很小，枚举最多放x

但还是不好放

考虑所有位置先都放上，然后删除最少使得合法

为了凑所有的位置都考虑到，把它当最大流

但是删除最少，所以最小费用

行列相关，左行点，右列点

S到行，流“能填位置”费0

列到T，流“能填位置”费0

i行到i列，流x，即枚举的最大个数

空位(i,j)，i行连j列，流1费0

最小费用最大流

意义：流过i行到i列的流量，象征留下一个芯片

流过费用为1的，象征把这个芯片删除。

最大流保证所有位置都考虑到了

最小费用使得最少。

可以发现最后的结果一定满足条件1

条件2？

最大流为flow，费用为cos，总共的位置（多出来的+必填）=sum

放置了tot=sum-cos

如果有x/tot<=A/B那么更新ans=max(ans,tot)
x一定时，tot越大，越可能比A/B小。和最小费用相符。

虽然可能x过大，但是答案一定可以枚举到。

代码：

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=;

const int P=;

const int inf=0x3f3f3f3f;

int n,A,B;

struct node{

    int nxt,to;

    int c,w;

}e[*(N*N+*N)+];

int hd[P],cnt=;

int s,t;

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

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    e[cnt].c=c;

    e[cnt].w=w;hd[x]=cnt;

    e[++cnt].nxt=hd[y];

    e[cnt].to=x;

    e[cnt].c=-c;

    e[cnt].w=;hd[y]=cnt;

}

int dis[P];

bool in[P];

int incf[P],pre[P];

queue<int>q;

int ans,flow,cos;

int l[N],h[N];

char mp[N][N];

bool spfa(){

    memset(dis,inf,sizeof dis);

    memset(pre,,sizeof pre);

    while(!q.empty()) q.pop();

    dis[s]=;

    incf[s]=inf;

    q.push(s);

    while(!q.empty()){

        int x=q.front();q.pop();

        in[x]=;

        for(reg i=hd[x];i;i=e[i].nxt){

            int y=e[i].to;

            if(e[i].w){

                if(dis[y]>dis[x]+e[i].c){

                    dis[y]=dis[x]+e[i].c;

                    pre[y]=i;

                    incf[y]=min(incf[x],e[i].w);

                    if(!in[y]){

                        in[y]=;

                        q.push(y);

                    }

                }

            }

        }

    }

    if(dis[t]==inf) return false;

    return true;

}

void upda(){

    int x=t;

    while(pre[x]){

        e[pre[x]].w-=incf[t];

        e[pre[x]^].w+=incf[t];

        x=e[pre[x]^].to;

    }

    flow+=incf[t];

    cos+=dis[t]*incf[t];

}

void EK(int lim){

    cos=;flow=;

    memset(hd,,sizeof hd);

    cnt=;

    s=,t=*n+;

    for(reg i=;i<=n;++i) {

        add(s,i,l[i],);

        add(i+n,t,h[i],);

        add(i,i+n,lim,);

    }

    for(reg i=;i<=n;++i){

        for(reg j=;j<=n;++j){

            if(mp[i][j]=='.') add(i,j+n,,);

        }

    }

    while(spfa()) upda();

}

void clear(){

    ans=-;

    for(reg i=;i<=n;++i) l[i]=n;

    for(reg j=;j<=n;++j) h[j]=n;

}

int main(){

    int o=;

    while(){

        rd(n);rd(A);rd(B);

        if(n==&&A==&&B==) break;

        ++o;

        clear();

        int can=;

        int alr=;

        for(reg i=;i<=n;++i){

            scanf("%s",mp[i]+);

            for(reg j=;j<=n;++j){

                if(mp[i][j]=='/') --l[i],--h[j];

                else ++can;

                if(mp[i][j]=='C') ++alr;

            }

        }

        for(reg x=;x<=n;++x){

            EK(x);

            int tot=can-cos;

            if(flow==can&&A*tot>=x*B) ans=max(ans,tot);

        }

        ans-=alr;

        printf("Case %d: ",o);

        if(ans<) printf("impossible");

        else printf("%d",ans);

        puts("");

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/1/8 10:23:22

*/

最小费用最大流可以考虑两个限制

最大流限制合法

费用流限制优秀

巴特西

[Wf2011]Chips Challenge

最新文章

热门文章