「TJOI2013」攻击装置

题目链接

\(solution\)

这道题和网络24题之骑士共存问题很相似

只是输入方式不一样而已

详细见:这儿
\(Code\)

#include<bits/stdc++.h>

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

#define rg register

using namespace std;

typedef long long ll;

int n,m,s,t,z,y,x;

inline int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9')  f= (c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9')  x=x*10+c-48,c=getchar();

    return f*x;

}

struct node{

    int to,next,v;

}a[400001];

int cnt,head[200001],cur[200001];

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

    a[++cnt].to=y;

    a[cnt].next=head[x];

    a[cnt].v=c;

    head[x]=cnt;

}

queue <int> q;

int dep[100001];

int bfs(){

    memset(dep,0,sizeof(dep));

    q.push(s),dep[s]=1;

    while(!q.empty()){

        int now=q.front();

        q.pop();

        for(int i=head[now];i;i=a[i].next){

            int v=a[i].to;

            if(!dep[v]&&a[i].v)

                q.push(v),dep[v]=dep[now]+1;

        }

    }

    if(dep[t]!=0)

        return 1;

    else

        return 0;

}

int dfs(int k,int list){

    if(k==t)

        return list;

    for(int &i=cur[k];i;i=a[i].next){

        int v=a[i].to;

        if(a[i].v&&dep[v]==dep[k]+1){

            int p=dfs(v,min(list,a[i].v));

            if(p){

                a[i].v-=p;

                if(i%2)

                    a[i+1].v+=p;

                else

                    a[i-1].v+=p;

                return p;

            }

        }

    }

    return 0;

}

int Dinic(){

    int ans=0;

    while(bfs()){

        for(int i=0;i<t;i++)

            cur[i]=head[i];

        int k=dfs(s,2147483);

        while(k)

            ans+=k,k=dfs(s,2147483);

    }

    return ans;

}

int f[201][201];

int fx[10]={0,1,1,-1,-1,2,2,-2,-2};

int fy[10]={0,2,-2,2,-2,1,-1,1,-1};

char S[1000];

int main(){

    n=read(),s=0,t=n*n+1;

    int sum=0;

    for(int i=1;i<=n;i++){

        cin>>S;

        for(int j=0;j<strlen(S);j++){

            f[i][j+1]=S[j]-'0';

            if(f[i][j+1])

                m++;

        }

    }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++){

            if(f[i][j])

                continue;

            if(((i+j)%2)==0)

                add((i-1)*n+j,t,1),add(t,(i-1)*n+j,0);

            else

                add(s,(i-1)*n+j,1),add((i-1)*n+j,s,0);

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            for(int k=1;k<=8;k++){

                int x=i+fx[k],y=j+fy[k],p=(x-1)*n+y;

                if(x>0&&y>0&&x<=n&&y<=n&&((i+j)%2)==1&&!f[i][j]&&!f[x][y])

                    add((i-1)*n+j,p,10000000),add(p,(i-1)*n+j,0);

            }

    int ans=Dinic();

    printf("%d",n*n-m-ans);

}
巴特西

「TJOI2013」攻击装置

题目链接

\(solution\)

\(Code\)

最新文章

热门文章
