「TJOI2013」循环格

题目链接

戳我

\(Solution\)

我们观察发现循环格要满足每个点的入度都为\(1\)

证明:

我们假设每个点的入读不一定为\(1\)，那么必定有一个或多个点的入度为0，那么则不满足循环格的定义，所以假设错误。所以每个点的入度必然为1。

所以这样我们就可以开始建图了。先进行拆点操作，将每个点拆成\(x\)和\(x'\)将\(x\)和\(S\)连接，流量为\(1\)，费用为\(0\)再将\(x'\)和\(T\)连接，流量为\(1\)，费用为\(0\)

最后对于每个点\(x\)将它和四周的\('\)点相连接。流量为1,费用的话在判断一下方向和字符是否相同，如果相同为\(0\)，不同为\(1\)

\(end.\)

\(Code\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

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-'0',c=getchar();

    return x*f;

}

struct node {

    int to,next,v,w;

} a[1000001];

int dis[10001],f[10001],pre[10001],fa[10001],s,t,n,m,head[10001],cnt,x,y,z,c;

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

    a[++cnt].to=y;

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

    a[cnt].v=c;

    a[cnt].w=v;

    head[x]=cnt;

}

queue < int > q;

int spfa() {

    q.push(s);

    memset(dis,127,sizeof(dis));

    memset(f,0,sizeof(f));

    f[s]=1,dis[s]=0;

    int inf=dis[s+1];

    while(!q.empty()) {

        int now=q.front();

        q.pop();

        f[now]=0;

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

            int v=a[i].to;

            if(dis[v]>dis[now]+a[i].w&&a[i].v) {

                dis[v]=dis[now]+a[i].w,pre[v]=i,fa[v]=now;

                if(!f[v])

                    f[v]=1,q.push(v);

            }

        }

    }

    if(dis[t]!=inf)

        return 1;

    return 0;

}

int ans1,ans;

void anser() {

    while(spfa()) {

        int minx=2147483647;

        for(int i=t; i!=s; i=fa[i])

            minx=min(minx,a[pre[i]].v);

        ans+=minx,ans1+=dis[t]*minx;

        for(int i=t; i!=s; i=fa[i])

            a[pre[i]].v-=minx,(pre[i]%2)?a[pre[i]+1].v+=minx:a[pre[i]-1].v+=minx;

    }

}

char hh[10]= {'0','D','U','L','R'};

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

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

char ss[101][101],l[1001];

int main() {

    int N=read(),M=read();

    s=0,t=N*M*10,n=N*M;

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

        add(s,i,1,0),add(i,s,0,0);

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

        add(i+n,t,1,0),add(t,i+n,0,0);

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

        cin>>l;

        for(int j=0; j<M; j++)

            ss[i][j+1]=l[j];

    }

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

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

            char pp=ss[i][j];

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

                int X=(i+fx[k]+N-1)%N+1,Y=(j+fy[k]+M-1)%M+1;

                int now=(i-1)*M+j,nex=(X-1)*M+n+Y,o=(pp==hh[k])^1;

                add(now,nex,1,o),add(nex,now,0,-o);

            }

        }

    anser();

    printf("%d",ans1);

}

巴特西

「TJOI2013」循环格

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章