设为首页 加入收藏

TOP

HDU 3605Escape（缩点+网络流之最大流）
2015-07-24 05:49:47 来源: 作者: 【大 中 小】 浏览:4次
Tags：HDU 3605Escape （缩点 网络 最大

?

本来打算昨天写两道题的，结果这个题卡住了，最后才发现是最后的判断条件出错了，判断满流的条件应该是与n的比较，竟然写成与所有星球总容量的比较了。（最近大脑短路。。）

这题也不是完全自己想的，没想到缩点这一技巧，由于n的数据范围太大，普通的建图方法会超时超内存，需要缩点，因为对于每个点来说，一共只有2^10种方法，而最多一共有10W个点，显然有很多点是重复的，这时可以采取缩点的方法，将重复的当成一个点来处理。这样数据范围就缩小到了1024个点，速度大大提升。

建图思路是建一源点与汇点，将每种方法与源点相连，权值为这种方法重复的次数，将每个星球与汇点相连，权值为每个星球的最大容量，再将每种方法与星球相连，权值为INF，最后判断是否满流。

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            using namespace std; const int INF=1e9; int head[2000], s, t, nv, n, cnt; int num[2000], d[2000], pre[2000], cur[2000], q[2000], fei[2000]; struct node { int u, v, next, cap; }edge[1000000]; 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(num,0,sizeof(num)); memset(d,-1,sizeof(d)); int f1=0, f2=0, i; q[f1++]=t; d[t]=0; num[0]=1; 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; } } } } int isap() { memcpy(cur,head,sizeof(cur)); int flow=0, i, u=pre[s]=s; bfs(); while(d[s]
           
            edge[cur[i]].cap) { f=edge[cur[i]].cap; pos=i; } } for(i=s;i!=t;i=edge[cur[i]].v) { edge[cur[i]].cap-=f; edge[cur[i]^1].cap+=f; } flow+=f; if(flow>=n) return flow; 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]; } } return flow; } int main() { int m, x, i, j, top, y, z, num, a[20]; while(scanf(%d%d,&n,&m)!=EOF) { memset(head,-1,sizeof(head)); memset(fei,0,sizeof(fei)); cnt=0; s=0; top=0; num=0; for(i=1;i<=n;i++) { x=0; for(j=1;j<=m;j++) { scanf(%d,&y); x=x*2+y; } fei[x]++; } for(i=1;i<=1100;i++) { if(fei[i]) { num++; } } t=num+m+1; nv=t+1; for(i=1;i<=1100;i++) { if(fei[i]) { //printf(--%d %d , i, fei[i]); top++; add(s,top,fei[i]); x=i; z=m+1; while(x) { y=x%2; z--; if(y) { add(top,z+num,INF); } //printf(--%d %d %d %d--,y, top, z, num); x=x/2; } //printf( ); } } for(i=1;i<=m;i++) { scanf(%d,&x); add(i+num,t,x); } x=isap(); if(x>=n) printf(YES ); else printf(NO ); } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Scramble String 下一篇：HDU 1535 Invitation Cards （POJ..

评论

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