首页 > 代码库 > BZOJ 3171 循环格

BZOJ 3171 循环格

重点:如果满流一定存在许多个欧拉回路。于是费用流。

#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#define maxv 500#define maxe 1000050#define maxn 20#define inf 2000000000using namespace std;int n,m,map[maxn][maxn],dis[maxv],nume=1,g[maxv],s,t,pree[maxv],prev[maxv];int dx[]={0,0,0,-1,1},dy[]={0,-1,1,0,0};char pp[maxn];bool vis[maxv];queue <int> q;struct edge{    int v,f,c,nxt;}e[maxe];void get(int x,int y){    if (pp[y-1]==L) map[x][y]=1;    else if (pp[y-1]==R) map[x][y]=2;    else if (pp[y-1]==U) map[x][y]=3;    else map[x][y]=4;}void addedge(int u,int v,int f,int c){    e[++nume].v=v;e[nume].f=f;e[nume].c=c;e[nume].nxt=g[u];g[u]=nume;    e[++nume].v=u;e[nume].f=0;e[nume].c=-c;e[nume].nxt=g[v];g[v]=nume;}int p(int x,int y){    return (x-1)*m+y;}void build(){    s=0;t=2*n*m+1;    for (int i=1;i<=n*m;i++)    {        addedge(s,i,1,0);        addedge(i+n*m,t,1,0);    }    for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)            for (int k=1;k<=4;k++)            {                int tx=(i+dx[k]+n)%n,ty=(j+dy[k]+m)%m;                if (!tx) tx=n;if (!ty) ty=m;                if ((tx==i) && (ty==j)) continue;                if (map[i][j]==k) addedge(p(i,j),n*m+p(tx,ty),1,0);                else addedge(p(i,j),n*m+p(tx,ty),1,1);            }}bool spfa(){    for (int i=s;i<=t;i++) {pree[i]=prev[i]=-1;dis[i]=inf;vis[i]=false;}    q.push(s);vis[s]=true;dis[s]=0;    while (!q.empty())    {        int head=q.front();q.pop();        for (int i=g[head];i;i=e[i].nxt)        {            int v=e[i].v;            if ((e[i].f) && (dis[v]>dis[head]+e[i].c))            {                dis[v]=dis[head]+e[i].c;                pree[v]=i;prev[v]=head;                if (!vis[v]) {q.push(v);vis[v]=true;}            }        }        vis[head]=false;    }    if (dis[t]==inf) return false;    return true;}int dinic(){    int u=t,low=inf;    while (u!=s)    {        low=min(low,e[pree[u]].f);        u=prev[u];    }    u=t;    while (u!=s)    {        e[pree[u]].f-=low;e[pree[u]^1].f+=low;        u=prev[u];    }    return dis[t]*low;}int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++)    {        scanf("%s",pp);        for (int j=0;j<m;j++) get(i,j+1);    }    build();    int min_cost=0;    while (spfa()) min_cost+=dinic();    printf("%d\n",min_cost);    return 0;}

 

BZOJ 3171 循环格