设为首页 加入收藏

TOP

HDU 3046Pleasant sheep and big big wolf（网络流之最小割）
2015-07-20 18:06:42 来源: 作者: 【大 中 小】 浏览:19次
Tags：HDU 3046Pleasant sheep and big wolf 网络 最小

题目地址：HDU 3046

最小割第一发！其实也没什么发不发的。。。最小割==最大流。。

入门题，但是第一次入手最小割连入门题都完全没思路。。。sad。。对最小割的本质还是了解的不太清楚。。

这题就是对每两个相邻的格子的边界都要进行加边，然后求最大流就OK了。

RE了好长时间，注意遍历加边的时候要从1开始，而不是0开始，因为0是源点的。。。（也许只有我才犯这种错误吧。。。）建图不多说了。。只要了解了最小割，建图还是很容易想的。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include
          
            using namespace std; const int INF=0x3f3f3f3f; int head[100000], source, sink, nv, cnt; int cur[100000], num[100000], d[100000], pre[100000], q[100000], mp[300][300]; struct node { int u, v, cap, next; } edge[10000000]; void add(int u, int v, int cap) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].next=head[v]; head[v]=cnt++; } void bfs() { memset(d,-1,sizeof(d)); memset(num,0,sizeof(num)); int f1=0, f2=0, i; d[sink]=0; num[0]=1; q[f1++]=sink; while(f1>=f2) { int u=q[f2++]; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]==-1) { d[v]=d[u]+1; num[d[v]]++; q[f1++]=v; } } } } void isap() { memcpy(cur,head,sizeof(cur)); bfs(); int flow=0, u=pre[source]=source, i; while(d[source]
           
            edge[cur[i]].cap) { f=edge[cur[i]].cap; pos=i; } } for(i=source;i!=sink;i=edge[cur[i]].v) { edge[cur[i]].cap-=f; edge[cur[i]^1].cap+=f; } flow+=f; u=pos; } for(i=cur[u];i!=-1;i=edge[i].next) { if(d[edge[i].v]+1==d[u]&&edge[i].cap) break; } if(i!=-1) { cur[u]=i; pre[edge[i].v]=u; u=edge[i].v; } else { if(--num[d[u]]==0) break; int mind=nv; for(i=head[u];i!=-1;i=edge[i].next) { if(mind>d[edge[i].v]&&edge[i].cap) { mind=d[edge[i].v]; cur[u]=i; } } d[u]=mind+1; num[d[u]]++; u=pre[u]; } } printf("%d\n",flow); } int main() { int n, m, i, j, num=0; while(scanf("%d%d",&n,&m)!=EOF) { num++; memset(head,-1,sizeof(head)); cnt=0; source=0; sink=n*m+1; nv=sink+1; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%d",&mp[i][j]); if(i!=1) add((i-1)*m+j,(i-2)*m+j,1); if(i!=n) add((i-1)*m+j,i*m+j,1); if(j!=1) add((i-1)*m+j,(i-1)*m+j-1,1); if(j!=m) add((i-1)*m+j,(i-1)*m+j+1,1); if(mp[i][j]==1) add(source,(i-1)*m+j,INF); else if(mp[i][j]==2) add((i-1)*m+j,sink,INF); } } printf("Case %d:\n",num); isap(); } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ 2243 || HDU 1372:Knight Mov.. 下一篇：HDU 1004 Let the Balloon Rise

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: