首页 > 代码库 > [hdu 3605]Escape

[hdu 3605]Escape

2024-07-21 13:23:25   226人阅读

这题的做法非常直观，却又非常不直观

先容许我吐一下槽吧~作者你的英语是读到火星上去了喵？

 

题目大体是说人类要移民，然后有 n 个人， m 个星球

每个人都有 m 个 0 、 1 数码表示他能否移民到该星球，每个星球有个最大人口容量

问是否有方案移民该 n 个人

 

乍一看很水，但是看看 n 的数据范围真是太感动人心了，有种这尼玛更本不是网络流的感脚——

但是 m 的范围只有 10 ！直觉告诉我似乎可以动手脚的样子喵？

状压！因为不需要输出方案，所以两个可移民方案相同的人完全可以视为同一人

然后点就被压到了 1024 以内，妥妥地过掉了~

我才不会说我连边连错害我调了半小时呢喵

 

  1 #include <cstdio>  2 #include <cstring>  3 #define min(x, y) ((x)<(y) ? (x):(y))  4 const int inf=0x7FFFFFFF;  5 const int sizeOfPoint=10050;  6 const int sizeOfEdge=500050;  7   8 int n, m, t;  9 int S, T; 10 int f[sizeOfPoint], a[sizeOfPoint]; 11  12 struct edge {int point, flow; edge * next, * pair;}; 13 edge memory[sizeOfEdge], * port=memory; 14 edge * e[sizeOfPoint]; 15 inline void clear() {port=memory; memset(e, 0, sizeof e); t=0; memset(f, 0, sizeof f);} 16 inline edge * newedge(int point, int flow, edge * next) {edge * ret=port++; ret->point=point; ret->flow=flow; ret->next=next; ret->pair=NULL; return ret;} 17 inline void build(int u, int v, int f) {e[u]=newedge(v, f, e[u]); e[v]=newedge(u, 0, e[v]); e[u]->pair=e[v]; e[v]->pair=e[u];} 18 int h[sizeOfPoint]; 19 inline bool bfs(); 20 inline int aug(); 21 inline int dinic(); 22  23 int main() 24 { 25     int x, state; 26  27     while (scanf("%d %d", &n, &m)!=EOF) 28     { 29         clear(); 30         for (int i=1;i<=n;i++) 31         { 32             state=0; 33             for (int j=0;j<m;j++) 34             { 35                 scanf("%d", &x); 36                 state|=x<<j; 37             } 38             if (!f[state]++) a[++t]=state; 39         } 40         S=0; T=t+m+1; 41         for (int i=1;i<=t;i++) 42         { 43             build(S, i, f[a[i]]); 44             for (int j=0;j<m;j++) if ((a[i]>>j)&1) 45                 build(i, t+j+1, f[a[i]]); 46         }     47         for (int i=1;i<=m;i++) 48         { 49             scanf("%d", &x); 50             build(t+i, T, x); 51         } 52  53         if (dinic()==n) printf("YES\n"); 54         else printf("NO\n"); 55     } 56  57     return 0; 58 } 59 inline bool bfs() 60 { 61     static int q[sizeOfPoint]; 62     int l=0, r=0; 63     memset(h, 0xFF, sizeof h); h[T]=0; 64     for (q[r++]=T;l<r;l++) 65     { 66         int u=q[l]; 67         for (edge * i=e[u];i;i=i->next) if (i->pair->flow && h[i->point]==-1) 68             h[q[r++]=i->point]=h[u]+1; 69     } 70     return h[S]>=0; 71 } 72 inline int aug() 73 { 74     static edge * t[sizeOfPoint], * path[sizeOfPoint]; 75     static int aug[sizeOfPoint]; 76     int flow=0; 77  78     memcpy(t, e, sizeof e); 79     memset(path, 0, sizeof path); 80     memset(aug, 0, sizeof aug); 81     aug[S]=inf; 82     for (int u=S; ; ) 83     { 84         if (u==T) 85         { 86             flow+=aug[T]; 87             for (edge * i=path[T];i;i=path[i->point]) 88             { 89                 i->pair->flow-=aug[T], i->flow+=aug[T]; 90                 aug[i->point]-=aug[T]; 91                 if (!aug[i->point]) h[i->point]=-1; 92             } 93             u=S; 94         } 95  96         edge *& i=t[u]; 97         for ( ;i && (!i->flow || h[u]!=h[i->point]+1);i=i->next); 98         if (i) 99         {100             path[i->point]=i->pair; aug[i->point]=min(aug[u], i->flow);101             u=i->point; i=i->next;102         }103         else104         {105             if (u==S) break;106             u=path[u]->point;107         }108     }109 110     return flow;111 }112 inline int dinic()113 {114     int ret=0, flow;115     while (bfs())116         while (flow=aug())117             ret+=flow;118     return ret;119 }
本傻调出翔系列

 

[hdu 3605]Escape


联系
我们