美文网首页信息学竞赛题解(IO题解)
BZOJ-1458: 士兵占领(网络流)

BZOJ-1458: 士兵占领(网络流)

作者: AmadeusChan | 来源:发表于2018-10-16 20:16 被阅读0次

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1458

    这道题我开始没有想出来,后来是在群上ORZ了某大神之后才知道可以用二分图匹配写的。(刚开始是用不等式消元建图写得快吐,后来果断放弃)做法如下:

    把每一行和每一列看成一个点,然后源点连每个行,容量为该行可行的格子数-需要的士兵数,每列连汇,容量为该列可行的格子数-需要的士兵数,然后对于每个可行点(i,j)行i连列j,容量1。跑一次最大流,用总可行格子数-流就是答案。

    代码:

    c83d70cf3bc79f3d7cdeea3fb8a1cd11728b2985.jpg.png
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
     
    using namespace std;
     
    #define MAXN 110
    #define MAXV 310
    #define clear(x) memset(x,0,sizeof(x))
    #define rep(i,x) for (int i=0;i++<x;)
    #define inf 0x7fffffff
     
    struct edge {
        edge *pair,*next;
        int t,f;
        edge () {
            next=pair=NULL;
        }
    } *head[MAXV];
     
    void Add(int s,int t,int f) {
        edge *p=new(edge);
        p->t=t,p->next=head[s],p->f=f;
        head[s]=p;
    }
     
    void AddEdge(int s,int t,int f) {
        Add(s,t,f),Add(t,s,0);
        head[s]->pair=head[t],head[t]->pair=head[s];
    }
     
    int S,T,n,m,k,sumn[MAXN],summ[MAXN],l[MAXN],r[MAXN],sum;
    bool f[MAXN][MAXN];
     
    edge *d[MAXV];
    int h[MAXV],gap[MAXV];
     
    int sap(int v,int flow) {
        if (v==T) return flow;
        int rec=0;
        for (edge *p=d[v];p;p=p->next) if (p->f&&h[v]==h[p->t]+1) {
            int ret=sap(p->t,min(flow-rec,p->f));
            p->f-=ret,p->pair->f+=ret,d[v]=p;
            if ((rec+=ret)==flow) return flow;
        }
        if (!(--gap[h[v]])) h[S]=T;
        gap[++h[v]]++,d[v]=head[v];
        return rec;
    }
     
    int maxflow() {
        clear(gap),clear(h);
        gap[0]=T;
        rep(i,T) d[i]=head[i];
        int flow=0;
        while (h[S]<T) flow+=sap(S,inf);
        return flow;
    }
     
    int main() {
        clear(sumn),clear(summ),clear(head);
        memset(f,true,sizeof(f));
        scanf("%d%d%d",&n,&m,&k);
        sum=n*m-k;
        rep(i,n) scanf("%d",&l[i]);
        rep(i,m) scanf("%d",&r[i]);
        while (k--) {
            int x,y;
            scanf("%d%d",&x,&y);
            sumn[x]++,summ[y]++,f[x][y]=false;
        }
        rep(i,n) if (sumn[i]+l[i]>m) {
            printf("JIONG!\n");
            return 0;
        }
        rep(i,m) if (summ[i]+r[i]>n) {
            printf("JIONG!\n");
            return 0;
        }
        S=n+m+1,T=n+m+2;
        rep(i,n) AddEdge(S,i,m-sumn[i]-l[i]);
        rep(i,m) AddEdge(n+i,T,n-summ[i]-r[i]);
        rep(i,n) rep(j,m) if (f[i][j]) AddEdge(i,n+j,1);
        printf("%d\n",sum-maxflow());
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:BZOJ-1458: 士兵占领(网络流)

        本文链接:https://www.haomeiwen.com/subject/rxkkzftx.html