DZY 's BLOG
Hello World!
dzy493941464
Music
BZOJ1066: [SCOI2007]蜥蜴【网络流】
自己YY出来了？估计应该是比较简单的网络流入门题吧。。
既然每个点(i,j)最多只能通过c[i][j]个蜥蜴。那么很自然地想到拆点。(i,j)→(i,j)'连上容量为c[i][j]的边。(i,j)为入点。(i,j)'为出点。
对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是c[i][j]。
然后n^4枚举在内部跳来跳去的情况。最后跑网络流就好了。
连T的边的时候我一直在傻×、、一开始算的是到(0,0)的距离≤d、、果然还是太弱了哎、、
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1000,maxm=500000,inf=1000000009;int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn],id[25][25];int S,T,n,m,k,tot=0,cnt=0,N=0; char s[25];inline void ae(int x,int y,int z){ p[tot]=y; c[tot]=z; n1[tot]=h[x]; h[x]=tot++; p[tot]=x; c[tot]=0; n1[tot]=h[y]; h[y]=tot++;}inline int bfs(){ memset(d,0xff,sizeof(d)); int r=d[q[0]=S]=0; for(int l=0;l<=r;l++) for(int k=h[q[l]];~k;k=n1[k]) if(c[k] && !~d[p[k]]) d[q[++r]=p[k]]=d[q[l]]+1; return ~d[T];}int dfs(int x=S,int lmt=inf){ if(x==T) return lmt; int flow; for(int &k=g[x];~k;k=n1[k]){ if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){ c[k]-=flow; c[k^1]+=flow; return flow; } }return 0;}int main(){ scanf("%d%d%d",&n,&m,&k); k; S=0; T=801; memset(h,0xff,sizeof(h)); for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]-'0'){ id[i][j]=++cnt; ae((id[i][j]<<1)-1,id[i][j]<<1,s[j]-'0'); if(min(min(i,n-i+1),min(j,m-j+1))<=k)ae(id[i][j]<<1,T,s[j]-'0'); }for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=1;ii<=n;ii++) for(int jj=1;jj<=m;jj++){ if(!id[i][j]||!id[ii][jj]) continue; if((ii-i)*(ii-i)+(jj-j)*(jj-j)<=k*k) ae(id[i][j]<<1,(id[ii][jj]<<1)-1,inf); }for(int i=1,j;i<=n;i++) for(scanf("%s",s+1),j=1;j<=m;j++) if(s[j]=='L'){ N++; if(id[i][j]) ae(S,(id[i][j]<<1)-1,1); }int An=0,f=0; while(bfs()){ memcpy(g,h,sizeof(h)); while(f=dfs()) An+=f;} printf("%d\n",N-An); return 0;} |
评论 (0)