首页 > 代码库 > bzoj1066
bzoj1066
首先,我们可以想到从源点向每个有蜥蜴的地方连边,然后拆点,因为我们不能把一个点连向多条边,这样修改边的时候不可以,所以拆个点,就可以了
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int inf=0x3f3f3f3f; struct edge { int to,nxt,f; }e[3011]; string s; int r,c,d,ans,cnt=1,tot; int board[1010][1010]; int g[3011],dist[3011]; void link(int u,int v,int f) { e[++cnt].nxt=g[u]; g[u]=cnt; e[cnt].f=f; e[cnt].to=v; } inline int Min(int x,int y) { return x<y?x:y; } inline int abs(int x) { return x<0?-x:x; } inline int Max(int x,int y) { return x>y?x:y; } inline void ins(int u,int v,int f) { link(u,v,f); link(v,u,0); } bool bfs() { queue<int>q; memset(dist,inf,sizeof(dist)); dist[0]=0; q.push(0); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=g[u];i;i=e[i].nxt) { int v=e[i].to; if(e[i].f&&dist[v]==inf) { dist[v]=dist[u]+1; q.push(v); } } } return dist[1010]!=inf; } int dfs(int u,int delta) { if(u==1010) return delta; int ret=0; for(int i=g[u];i&δi=e[i].nxt) { int v=e[i].to; if(e[i].f&&dist[v]==dist[u]+1) { int dd=dfs(v,Min(e[i].f,delta)); delta-=dd; e[i].f-=dd; e[i^1].f+=dd; ret+=dd; } } return ret; } inline void dinic() { while(bfs()) { ans+=dfs(0,inf); } printf("%d",tot-ans); } int main() { cin>>r>>c>>d; for(int i=1;i<=r;i++) { cin>>s; for(int j=0;j<s.length();j++) { board[i][j+1]=s[j]-‘0‘; } } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(board[i][j]) { ins((i-1)*c+j,(i-1)*c+j+r*c,board[i][j]); if(j-d<=0||j+d>c||i-d<=0||i+d>r) { ins((i-1)*c+j+r*c,1010,board[i][j]); } for(int a=Max(1,i-d);a<=Min(i+d,r);a++) for(int b=Max(1,j-d);b<=Min(j+d,c);b++) if(abs(a-i)+abs(b-j)<=d&&board[a][b]) ins((i-1)*c+j+r*c,(a-1)*c+b,inf); } for(int i=1;i<=r;i++) { cin>>s; for(int j=0;j<s.length();j++) { if(s[j]==‘L‘) {tot++; ins(0,(i-1)*c+j+1,1);} } } dinic(); return 0; }
bzoj1066
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。