首页 > 代码库 > HDU 3605 Escape（最大流+缩点转换）

HDU 3605 Escape（最大流+缩点转换）

2024-07-16 15:42:02   216人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3605

题目很简单，要求的就是最后能搬到星球上去的人的个数。刚开始看到，知道是最大流，就把人和星球都设为点，能生存就连线，权值为1，最后建立超级源点和超级汇点。求出最大流量即可。先是RE，开大数组后TLE。仔细算了，光光人到星球的便就可达到100w了，超时的概率太大了。后来找了解题报告，知道了缩点这一说，因为星球个数m最大只有10个，所以每个人最多只有1024种情况，把这每一种情况设为点（这里很抽象），将之与符合情况的星球相连。边流量就是这种情况总的人数。最后每个星球以限定居住人数为边流量连超级汇点。建图完成后就可以用最大流求解了。

  1 /*Dinic算法求最大流*/  2 #include<stdio.h>  3 #include<string.h>  4 #define point_MAX 100025  5 #define edge_MAX 10000000  6 #define INF_MAX 999999999  7 #include<iostream>  8 using namespace std;  9 struct EDGE 10 { 11     int to;/*指向的点*/ 12     int next;/*指向的下一条邻边*/ 13     int w;/*权值*/ 14 }edge[edge_MAX]; 15 int len;/*边的数量*/ 16 int point[point_MAX]; 17 int Vertex,Edge; 18 int d[point_MAX]; 19 void init()/*初始化*/ 20 { 21     len=0; 22     memset(point,0,sizeof(point)); 23 } 24 int add_edge(int a,int b,int w)/*添加由a指向b的权值为w的边*/ 25 { 26     len++; 27     edge[len].w=w; 28     edge[len].to=b; 29     edge[len].next=point[a]; 30     point[a]=len; 31     return 0;/*无重边，插入*/ 32 } 33 int bfs(int s) 34 { 35     int q[point_MAX],front=0,rear=1,j,t,i; 36     q[0]=s; 37     memset(d,-1,sizeof(d));/**/ 38     d[s]=0; 39     while(front<rear) 40     { 41        t=q[front++]; 42          for(j=point[t];j;j=edge[j].next) 43          { 44             if(d[edge[j].to]==-1&&edge[j].w>0) 45             { 46              d[edge[j].to]=d[t]+1; 47            q[rear++]=edge[j].to;/*逐层增加*/ 48         } 49          } 50     } 51     if(d[Vertex]>=0) 52        return 1; 53     return 0; 54 } 55 long long min(long long a,long long b) 56 { 57     return a<b?a:b; 58 } 59 long long dinic(int t,long long sum)/*寻找增广路*/ 60 { 61     int i,os,j; 62     long long a; 63     if(t==Vertex)/*如果已经找到汇点，返回sum*/ 64       return sum; 65     os=sum; 66     for(i=point[t];i&&sum;i=edge[i].next) 67     { 68        if(d[edge[i].to]==d[t]+1&&edge[i].w>0)/*可行流，即增广路*/ 69        { 70            a=dinic(edge[i].to,min(sum,edge[i].w)); 71            edge[i].w-=a; 72            for(j=point[edge[i].to];edge[j].to!=t;j=edge[j].next); 73            edge[j].w+=a;/*处理反向边*/ 74            sum-=a; 75        } 76     } 77     return os-sum; 78 } 79 long long DINIC(int s)/*DINIC算法*/ 80 { 81      long long ans=0; 82      while(bfs(s))/*遍历整个图，判断是否已经完成最大流*/ 83        ans+=dinic(s,INF_MAX);/*添加所能增加的流量*/ 84      return ans; 85 } 86  87 int main() 88 { 89     int n,m,x,a[2005]; 90     int s=0,t=1050; 91     while(scanf("%d%d",&n,&m)!=EOF) 92     { 93         init(); 94         memset(a,0,sizeof(a)); 95         for(int i=1;i<=n;i++) 96         { 97             int k=0; 98             for(int j=0;j<m;j++) 99             {100                 scanf("%d",&x);101                 if(x)102                 {103                     k|=1<<j;104                 }105             }106             a[k]++;107         }108 109         for(int i=1;i<=(1<<m);i++)110         {111             if(a[i-1])112             {113                 add_edge(s,i,a[i-1]);114                 add_edge(i,s,0);115                 for(int j=0;j<m;j++)116                     if((i-1)&(1<<j))117                     {118                         add_edge(i,j+10+(1<<m),a[i-1]);119                         add_edge(j+10+(1<<m),i,0);120                     }121             }122         }123         for(int i=0;i<m;i++)124         {125             scanf("%d",&x);126             add_edge(i+(1<<m)+10,t,x);127             add_edge(t,i+(1<<m)+10,0);/*添加反向边*/128 129         }130         Vertex=t;131         int ans=DINIC(0);132         //cout<<ans<<endl;133         if(ans>=n)cout<<"YES"<<endl;134         else cout<<"NO"<<endl;135     }136     return 0;137 }
View Code

 


联系
我们