P3376 【模板】网络最大流

Dinic算法

#include <bits/stdc++.h> using namespace std; const int inf=1<<29; const int N=10050; const int M=100050; int n,m,s,t,maxflow; int fir[N],tot=1,nxt[M<<1],to[M<<1],w[M<<1],d[N]; queue<int> q; void add(int x,int y,int z){ nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;w[tot]=z; nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;w[tot]=0; } inline int read(){ int cnt=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-f;c=getchar();} while(isdigit(c)){cnt=(cnt<<3)+(cnt<<1)+(c&15);c=getchar();} return cnt*f; } bool bfs_(){ memset(d,0,sizeof(d));while(q.size()) q.pop(); q.push(s);d[s]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=fir[x];i;i=nxt[i]){ int y=to[i]; if(w[i]&&!d[y]){ q.push(y); d[y]=d[x]+1; if(y==t) return 1; } } } return 0; } int dinic(int x,int flow){ if(x==t) return flow; int rest=flow,k; for(int i=fir[x];i&&rest;i=nxt[i]){ int y=to[i]; if(d[y]==d[x]+1&&w[i]){ k=dinic(y,min(w[i],rest)); if(!k) d[y]=0; w[i]-=k;w[i^1]+=k;rest-=k; } } return flow-rest; } int main(){ n=read(),m=read(),s=read(),t=read(); tot=1; int u,v,val; for(int i=1;i<=m;i++){ u=read(),v=read(),val=read();add(u,v,val); } int flow=0; while(bfs_()){ while(flow=dinic(s,inf)) maxflow+=flow; } printf("%d",maxflow); return 0; }

P2472 [SCOI2007]蜥蜴

重点在于建边：

1.建立一个虚的源点$s$和一个虚的汇点$t$ 2.$s$朝每个有蜥蜴的石柱建一条长度为$1$的边(计算有几只蜥蜴能使源点和汇点连通，即能跳出去) 3.$t$朝每个与边界距离不超过$d$的点建一条长度为$inf$的边(不计数量的蜥蜴达到这些石柱后能跳出去) 4.将每个石柱拆成两个点，两个点之间建一条长度为$d$的边(表示最多能通过几只蜥蜴) 然后跑一遍$Dinic$即可

#include <bits/stdc++.h> using namespace std; const int inf=1<<29; const int N=25000; const int M=350000; queue<int> q; char lir[N][N]; int d_[N]; int r,c,d; int T,s; int Map[60][60],a[60][60]; int fir[N],to[M<<1],w[M<<1],nxt[M<<1],tot=1; int cnt; void add(int x,int y,int z){ nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;w[tot]=z; nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;w[tot]=0; } bool pd(int x,int y){if(x<=d||y<=d||(r-x+1)<=d||(c-y+1)<=d) return 1;return 0;} //注意判断是否超界的边界条件 bool bfs_(){ memset(d_,0,sizeof(d_)); while(!q.empty()) q.pop(); q.push(s);d_[s]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=fir[x];i;i=nxt[i]){ int y=to[i]; if(w[i]&&!d_[y]){d_[y]=d_[x]+1;q.push(y);if(y==T) return 1;} } } return 0; } int maxflow=0; int dinic(int x,int flow){ if(x==T) return flow; int rest=flow,k; for(int i=fir[x];i&&rest;i=nxt[i]){ int y=to[i]; if(w[i]&&d_[y]==d_[x]+1){ k=dinic(y,min(rest,w[i])); if(!k) d_[y]=0; w[i]-=k;w[i^1]+=k;rest-=k; } } return flow-rest; } int num=0; inline int read(){ int cnt=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-') f=-f;c=getchar();} while(isdigit(c)){cnt=(cnt<<3)+(cnt<<1)+(c&15);c=getchar();} return cnt*f; } int main(){ s=0; r=read(),c=read(),d=read(); T=r*c*2+5; for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){a[i][j]=++num;}} for(int i=1;i<=r;i++){scanf("%s",lir[i]+1);} for(int i=1;i<=r;i++){for(int j=1;j<=c;++j){Map[i][j]=lir[i][j]^48;}} for(int i=1;i<=r;i++){scanf("%s",lir[i]+1);} for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ if(Map[i][j]){ add(a[i][j],a[i][j]+r*c,Map[i][j]); if(pd(i,j)){add(a[i][j]+r*c,T,inf);} } } } for(int i=1;i<=r;++i){ for(int j=1;j<=c;++j){ for(int k=1;k<=r;++k){ for(int p=1;p<=c;p++){ if(i==k&&j==p) continue; if(Map[i][j]&&Map[k][p]) if((i-k)*(i-k)+(j-p)*(j-p)<=d*d){ add(a[i][j]+r*c,a[k][p],inf); } } } } } for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ if(lir[i][j]=='L') add(s,a[i][j],1),++cnt; } } int flow=0; while(bfs_()){ while(flow=dinic(s,inf)) maxflow+=flow; } int ans=cnt-maxflow; printf("%d",ans); return 0; }