网络流 E - Escape HDU - 3605-白红宇

网络流 E - Escape HDU - 3605

阅读量：4358 次

发布时间：2019-06-07

本文共 3354 字，大约阅读时间需要 11 分钟。

2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.

InputMore set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.

The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..

0 <= ai <= 100000

OutputDetermine whether all people can live up to these stars

If you can output YES, otherwise output NO.

Sample Input

1 1112 21 01 01 1

Sample Output

YESNO 题目大意：就是星球移民，不同的人对不同的星球适应情况不同，给你m个人n个星球和每个人对星球的适应情况，和每一个星球最大承载人数，让你求是否可以全部成功移民。

这个题目是一个比较明显的网络流，但是dinic的复杂度是n*n*m，所以这个直接跑网络流肯定会超时。

然后我就T了，虽然知道自己超时了，不过并没有想到怎么解决。

然后搜题解，就看到了状态压缩。

就是因为m=10，所以可以去考虑可能有些人对星球的适应情况是一样的，这个要用二进制的方式去转化

怎么个状态压缩呢？

就是因为可能有些人对星球的适应情况完全相同，所以就把人对星球的适应状况压缩成只含有01的数字。

然后用map存储，这个之后就是建图了，

建图你只要知道，你只需要利用map的数据建图就可以了，建好图map数组就没什么用了，所以你不需要一个对应关系。

这个建图就看代码吧。

这个卡cin

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #define inf 0x3f3f3f3fusing namespace std;const int maxn = 1e5 + 100;typedef long long ll;int s, t, n, m;struct node{ int from, to, cap, flow; node(int from=0,int to=0,int cap=0,int flow=0):from(from),to(to),cap(cap),flow(flow){}};vector
             
              e;vector
              
               G[maxn];void add(int u,int v,int c){ e.push_back(node(u, v, c, 0)); e.push_back(node(v, u, 0, 0)); int m = e.size(); G[u].push_back(m - 2); G[v].push_back(m - 1);}int level[maxn], iter[maxn];void bfs(int s){ queue
               
                que; que.push(s); memset(level, -1, sizeof(level)); level[s] = 0; while(!que.empty()) { int u = que.front(); que.pop(); for(int i=0;i
                
                 now.flow&&level[now.to]<0) { level[now.to] = level[u] + 1; que.push(now.to); } } }}int dfs(int u,int v,int f){ if (u == v) return f; for(int &i=iter[u];i
                 
                  now.flow&&level[now.to]>level[u]) { int d = dfs(now.to, v, min(f, now.cap - now.flow)); if(d>0) { now.flow += d; e[G[u][i] ^ 1].flow -= d; return d; } } } return 0;}map
                  
                   mp;int dinic(){ int flow = 0; while(1) { bfs(s); if (level[t] < 0) return flow; for (int i = s; i <= t; i++) iter[i] = 0; int f; while ((f = dfs(s, t, inf)) > 0) flow += f; }}void init(){ for (int i = 0; i <= n+m+5; i++) G[i].clear(); e.clear(); mp.clear();}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { init(); s = 0; for(int i=1;i<=n;i++) { int ret = 0; for(int j=1;j<=m;j++) { int x; scanf("%d", &x); ret = ret + (x << j); } mp[ret]++; } int cnt = mp.size(); int num = 0; map
                   
                    ::iterator p; for(p=mp.begin();p!=mp.end(); p++) { num++; for(int i=1;i<=m;i++) { if ((p->first)&(1 << i)) { add(num, cnt + i, p->second); } } add(s, num, p->second); } t = num + m + 1; for(int i=1;i<=m;i++) { int x; scanf("%d", &x); add(num + i, t, x); } int ans = dinic(); if (ans >= n) printf("YES\n"); else printf("NO\n"); } return 0;}

转载于:https://www.cnblogs.com/EchoZQN/p/10746914.html

你可能感兴趣的文章

linux安装nginx映射目录,centos8自定义目录安装nginx(教程详解)