首页 > 代码库 > BZOJ 3171 循环格（费用流）

BZOJ 3171 循环格（费用流）

2024-07-09 00:26:42   226人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=3171

题意：


思路：若能构成循环，则每个格子的入度出度均为1。因此将每个点拆成两个点x1,x2，分别作为出点和入点。出点向周围四个点的入点连边，流1，费用视该格子的字母而定。该格子的字母正好是这个方向则费用为0否则为1。原点S向每个出点连边，流量1费用0；每个入点向汇点连边，流量1费用0。求最小费用最大流即可。

 

struct node{    int u,v,next,cost,cap;};node edges[N];int head[N],e;void add(int u,int v,int cap,int cost){    edges[e].u=u;    edges[e].v=v;    edges[e].cap=cap;    edges[e].cost=cost;    edges[e].next=head[u];    head[u]=e++;}void Add(int u,int v,int cap,int cost){    add(u,v,cap,cost);    add(v,u,0,-cost);}int pre[N],F[N],C[N],visit[N];int SPFA(int s,int t,int n){    int i;    for(i=0;i<=n;i++) F[i]=0,C[i]=INF,visit[i]=0;    queue<int> Q;    Q.push(s); F[s]=INF; C[s]=0;    int u,v,cost,cap;    while(!Q.empty())    {        u=Q.front();        Q.pop();                visit[u]=0;        for(i=head[u];i!=-1;i=edges[i].next)        {            if(edges[i].cap>0)            {                v=edges[i].v;                cost=edges[i].cost;                cap=edges[i].cap;                if(C[v]>C[u]+cost)                {                    C[v]=C[u]+cost;                    F[v]=min(F[u],cap);                    pre[v]=i;                    if(!visit[v]) visit[v]=1,Q.push(v);                }            }        }    }    return F[t];}int MCMF(int s,int t,int n){    int ans=0,i,x,temp;    while(temp=SPFA(s,t,n))    {        for(i=t;i!=s;i=edges[pre[i]].u)        {            x=pre[i];            ans+=edges[x].cost*temp;            edges[x].cap-=temp;            edges[x^1].cap+=temp;        }    }    return ans;}int a[20][20][2],s,t,n,m;char S[20][20];int main(){    RD(n,m);    int i,j,k=0;    FOR1(i,n) FOR1(j,m)     {        a[i][j][0]=++k;        a[i][j][1]=++k;    }    s=0; t=++k;    FOR1(i,n) RD(S[i]+1);    int L,R,U,D;    clr(head,-1);    FOR1(i,n) FOR1(j,m)    {        if(S[i][j]==‘U‘) U=0;         else U=1;        if(S[i][j]==‘D‘) D=0;        else D=1;        if(S[i][j]==‘L‘) L=0;        else L=1;        if(S[i][j]==‘R‘) R=0;        else R=1;        if(i==1) Add(a[i][j][0],a[n][j][1],1,U);        else Add(a[i][j][0],a[i-1][j][1],1,U);                if(i==n) Add(a[i][j][0],a[1][j][1],1,D);        else Add(a[i][j][0],a[i+1][j][1],1,D);                if(j==1) Add(a[i][j][0],a[i][m][1],1,L);        else Add(a[i][j][0],a[i][j-1][1],1,L);                if(j==m) Add(a[i][j][0],a[i][1][1],1,R);        else Add(a[i][j][0],a[i][j+1][1],1,R);                Add(s,a[i][j][0],1,0);        Add(a[i][j][1],t,1,0);    }    PR(MCMF(s,t,t));}

 

 

 


联系
我们