1 条题解
-
1
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; queue <int> q; const int maxn=807; const int maxm=100007; const int inf=0x7f7f7f7f; struct E{ int u,v,cf; }e[maxm];//cf是指流量 #define cf(i) e[i].cf int first[maxn],nt[maxm],ES=1; inline void addE(int u,int v,int cf) { e[++ES]=(E){u,v,cf}; nt[ES]=first[u]; first[u]=ES; return ; } inline void add(int u,int v,int cf)//网络瘤专用加双边 { addE(u,v,cf);addE(v,u,0); return ; } int N,M,S,T; char m1[27][27],m2[27][27]; inline int num(int i,int j)//根据一个点的坐标得到其入点编号 { return (i-1)*M+j; } int d,all,ans; inline void linkE(int u,int i,int j)//从编号u连向 (i,j) { if(i<1||i>N||j<1||j>M)//落在图外直接连到T { add(u,T,inf); return ; } if(m1[i][j]=='0') return ; add(u,num(i,j),inf); return ; } inline void link(int i,int j)//点(i,j)连边 { if(m1[i][j]=='0') return ; add(num(i,j),num(i,j)+all,m1[i][j]-'0'); if(m2[i][j]=='L') add(S,num(i,j),1),ans++;//是蜥蜴,顺便统计蜥蜴只数 if(i==1||j==1||i==N||j==M) add(num(i,j)+all,T,inf); int u=num(i,j)+all; //最没营养的一部分 if(d>=1) { linkE(u,i-1,j);linkE(u,i+1,j); linkE(u,i,j-1);linkE(u,i,j+1); } if(d>=2) { linkE(u,i-2,j);linkE(u,i+2,j); linkE(u,i,j-2);linkE(u,i,j+2); linkE(u,i-1,j-1);linkE(u,i-1,j+1); linkE(u,i+1,j-1);linkE(u,i+1,j+1); } if(d>=3) { linkE(u,i-3,j);linkE(u,i+3,j);linkE(u,i,j-3);linkE(u,i,j+3); linkE(u,i-2,j-2);linkE(u,i-2,j+2);linkE(u,i+2,j-2);linkE(u,i+2,j+2); linkE(u,i-1,j-2);linkE(u,i-1,j+2);linkE(u,i+1,j-2);linkE(u,i+1,j+2); linkE(u,i-2,j-1);linkE(u,i-2,j+1);linkE(u,i+2,j-1);linkE(u,i+2,j+1); } if(d>=4) { linkE(u,i-4,j);linkE(u,i+4,j);linkE(u,i,j-4);linkE(u,i,j+4); linkE(u,i-1,j-3);linkE(u,i-1,j+3);linkE(u,i+1,j-3);linkE(u,i+1,j+3); linkE(u,i-3,j-1);linkE(u,i-3,j+1);linkE(u,i+3,j-1);linkE(u,i+3,j+1); linkE(u,i-3,j-2);linkE(u,i-3,j+2);linkE(u,i+3,j-2);linkE(u,i+3,j+2); linkE(u,i-2,j-3);linkE(u,i-2,j+3);linkE(u,i+2,j-3);linkE(u,i+2,j+3); } //呜呜终于写完了 return ; } //Dinic最大流部分 int cur[maxn],cnt[maxn]; inline bool BFS() { memset(cnt,0,sizeof(cnt)); cnt[S]=1; q.push(S); int u,v; while(!q.empty()) { u=q.front();q.pop(); for(register int i=first[u];i;i=nt[i]) { v=e[i].v; if(cf(i)>0&&!cnt[v]) { cnt[v]=cnt[u]+1; q.push(v); } } } return cnt[T]!=0; } inline int dfs(int u,int f) { if(u==T) return f; int d,v,sum=0; for(register int &i=cur[u];i;i=nt[i])//cur数组是 当前弧优化 { v=e[i].v; if(cf(i)>0&&cnt[v]==cnt[u]+1) { d=dfs(v,min(f,cf(i))); if(d>0) { f-=d;sum+=d; cf(i)-=d;cf(i^1)+=d; if(f<=0) return sum; } } } return sum; } int main() { scanf("%d%d%d",&N,&M,&d); T=N*M*2+1;all=N*M;//入点编号为u的点的出点为u+all for(register int i=1;i<=N;i++) scanf("%s",m1[i]+1); for(register int i=1;i<=N;i++) scanf("%s",m2[i]+1); for(register int i=1;i<=N;i++) for(register int j=1;j<=M;j++) link(i,j); while(BFS()) { memcpy(cur,first,sizeof(cur)); ans-=dfs(S,inf);//流量都是跑出去的蜥蜴,要求剩下的蜥蜴。 //在连边函数里面已经统计了蜥蜴数量,减去就可以 } printf("%d",ans); return 0; }
- 1
信息
- ID
- 1066
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 41
- 已通过
- 22
- 上传者