题目描述

费用流

容易发现不能移到另一个棋子上这个限制无用。
然后随便费用流。

#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=500+10,maxm=1000000+10,inf=1000000000;
int d[maxn*2],now[maxn*2],h[maxn*2],go[maxm*2],dis[maxm*2],co[maxm*2],fx[maxm*2],next[maxm*2];
int dl[maxn*maxn][2],id[maxn][maxn],di[maxn][maxn],f[maxn][maxn];
int st[8][2];
bool bz[maxn*2],pd[maxn][maxn],vis[maxn][maxn];
int i,j,k,l,r,c,s,t,n,m,a,b,x,y,tot,top,head,tail,tmp,ans;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
char get(){char ch=getchar();while (ch!='.'&&ch!='*') ch=getchar();return ch;
}
void add(int x,int y,int z,int c,int d){go[++tot]=y;dis[tot]=z;co[tot]=c;fx[tot]=tot+d;next[tot]=h[x];h[x]=tot;
}
void work(int xx,int yy){int i,j,x,y,nx,ny;fo(i,1,r)fo(j,1,c)pd[i][j]=vis[i][j];head=0;tail=1;f[xx][yy]=0;pd[xx][yy]=1;dl[1][0]=xx;dl[1][1]=yy;while (headx=dl[++head][0];y=dl[head][1];fo(i,0,7){nx=x+st[i][0];ny=y+st[i][1];if (nx<1||nx>r||ny<1||ny>c||pd[nx][ny]) continue;pd[nx][ny]=1;f[nx][ny]=f[x][y]+1;dl[++tail][0]=nx;dl[tail][1]=ny;}}fo(i,1,r)fo(j,1,c)if (di[i][j]){if (!pd[i][j]) continue;add(id[xx][yy],di[i][j],1,f[i][j],1);add(di[i][j],id[xx][yy],0,-f[i][j],-1);}
}
int dfs(int x,int flow,int cost){bz[x]=1;if (x==t){tmp+=flow;ans+=flow*cost;return flow;}int r=now[x],k;while (r){if (!bz[go[r]]&&dis[r]&&d[x]==d[go[r]]+co[r]){k=dfs(go[r],min(flow,dis[r]),cost+co[r]);if (k){dis[r]-=k;dis[fx[r]]+=k;now[x]=r;return k;}}r=next[r];}return now[x]=0;
}
bool change(){int i,r,tmp=inf;fo(i,s,t)if (bz[i]){r=h[i];while (r){if (!bz[go[r]]&&dis[r]&&d[go[r]]+co[r]-d[i]next[r];}}if (tmp==inf) return 0;fo(i,s,t)if (bz[i]) d[i]+=tmp;
}
int main(){freopen("willow.in","r",stdin);freopen("willow.out","w",stdout);r=read();c=read();n=read();a=read();b=read();st[0][0]=a;st[0][1]=b;st[1][0]=a;st[1][1]=-b;st[2][0]=-a;st[2][1]=-b;st[3][0]=-a;st[3][1]=b;swap(a,b);st[4][0]=a;st[4][1]=b;st[5][0]=a;st[5][1]=-b;st[6][0]=-a;st[6][1]=-b;st[7][0]=-a;st[7][1]=b;fo(i,1,r)fo(j,1,c)if (get()=='*') vis[i][j]=1;s=top=1;t=2*n+2;fo(i,1,n){j=read();k=read();id[j][k]=++top;add(s,top,1,0,1);add(top,s,0,0,-1);}fo(i,1,n){j=read();k=read();di[j][k]=++top;add(top,t,1,0,1);add(t,top,0,0,-1);}fo(i,1,r)fo(j,1,c)if (id[i][j]) work(i,j);do{fo(i,s,t) now[i]=h[i];fill(bz+s,bz+t+1,0);while (dfs(s,inf,0)) fill(bz+s,bz+t+1,0);}while (change());if (tmpprintf("-1\n");else printf("%d\n",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！