首页 > 代码库 > bzoj1001狼抓兔子
bzoj1001狼抓兔子
这题就一个裸的网络流吧,其实也可以用最短路。
主要就是建边的时候注意一下,其他就没有了。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <queue> 5 using namespace std; 6 const int N=1000010; 7 const int inf=1e9+7; 8 struct edge { 9 int v,next,c,f; 10 }e[N*6]; 11 int k=1,head[N],vis[N],dep[N],cur[N]; 12 int n,m,T; 13 int read() { 14 char c=getchar();int x=0; 15 while (c<‘0‘||c>‘9‘) c=getchar(); 16 while (c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); 17 return x; 18 } 19 void adde(int u,int v,int c) { 20 e[k].v=v;e[k].c=c;e[k].next=head[u];head[u]=k++; 21 } 22 queue <int> q; 23 bool bfs(int s,int t,int tim) { 24 dep[s]=0;vis[s]=tim; 25 q.push(s); 26 while (!q.empty()) { 27 int u=q.front();q.pop(); 28 for (int i=head[u];~i;i=e[i].next) { 29 int v=e[i].v; 30 if ((tim^vis[v])&&e[i].c>e[i].f) { 31 dep[v]=dep[u]+1;vis[v]=tim;q.push(v); 32 } 33 } 34 } 35 return tim==vis[t]; 36 } 37 38 int dfs(int u,int t,int F) { 39 if (u==t||F==0) return F; 40 int tot=0,f; 41 for (int &i=cur[u];~i;i=e[i].next) { 42 int v=e[i].v; 43 if (dep[v]==dep[u]+1&&vis[v]==T&&(f=dfs(v,t,min(F,e[i].c-e[i].f)))>0) { 44 tot+=f,F-=f; 45 e[i].f+=f,e[i^1].f-=f; 46 if (F==0) break; 47 } 48 } 49 return tot; 50 } 51 52 void dinic() { 53 int ans=0; 54 while (bfs(1,n*m,++T)) { 55 for (int i=1;i<=n*m;i++) cur[i]=head[i]; 56 ans+=dfs(1,n*m,inf); 57 } 58 printf("%d\n",ans); 59 } 60 61 int main() 62 { 63 memset(head,-1,sizeof(head)); 64 n=read();m=read(); 65 for (int i=1,x=0;i<=n;i++) { 66 x++; 67 for (int j=1;j<m;j++,x++) { 68 int w=read(); 69 adde(x,x+1,w);adde(x+1,x,w); 70 } 71 } 72 for (int i=1,x=1;i<n;i++) { 73 for (int j=1;j<=m;j++,x++) { 74 int w=read(); 75 adde(x,x+m,w);adde(x+m,x,w); 76 } 77 } 78 for (int i=1,x=0;i<n;i++) { 79 x++; 80 for (int j=1;j<m;j++,x++) { 81 int w=read(); 82 adde(x,x+m+1,w);adde(x+m+1,x,w); 83 } 84 } 85 dinic(); 86 return 0; 87 }
bzoj1001狼抓兔子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。