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

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