[hdu 3605]Escape

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

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

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

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

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

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

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

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

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

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

 #include <cstdio>

 #include <cstring>

 #define min(x, y) ((x)<(y) ? (x):(y))

 const int inf=0x7FFFFFFF;

 const int sizeOfPoint=;

 const int sizeOfEdge=;

 int n, m, t;

 int S, T;

 int f[sizeOfPoint], a[sizeOfPoint];

 struct edge {int point, flow; edge * next, * pair;};

 edge memory[sizeOfEdge], * port=memory;

 edge * e[sizeOfPoint];

 inline void clear() {port=memory; memset(e, , sizeof e); t=; memset(f, , sizeof f);}

 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;}

 inline void build(int u, int v, int f) {e[u]=newedge(v, f, e[u]); e[v]=newedge(u, , e[v]); e[u]->pair=e[v]; e[v]->pair=e[u];}

 int h[sizeOfPoint];

 inline bool bfs();

 inline int aug();

 inline int dinic();

 int main()

 {

     int x, state;

     while (scanf("%d %d", &n, &m)!=EOF)

     {

         clear();

         for (int i=;i<=n;i++)

         {

             state=;

             for (int j=;j<m;j++)

             {

                 scanf("%d", &x);

                 state|=x<<j;

             }

             if (!f[state]++) a[++t]=state;

         }

         S=; T=t+m+;

         for (int i=;i<=t;i++)

         {

             build(S, i, f[a[i]]);

             for (int j=;j<m;j++) if ((a[i]>>j)&)

                 build(i, t+j+, f[a[i]]);

         }

         for (int i=;i<=m;i++)

         {

             scanf("%d", &x);

             build(t+i, T, x);

         }

         if (dinic()==n) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

 inline bool bfs()

 {

     static int q[sizeOfPoint];

     int l=, r=;

     memset(h, 0xFF, sizeof h); h[T]=;

     for (q[r++]=T;l<r;l++)

     {

         int u=q[l];

         for (edge * i=e[u];i;i=i->next) if (i->pair->flow && h[i->point]==-)

             h[q[r++]=i->point]=h[u]+;

     }

     return h[S]>=;

 }

 inline int aug()

 {

     static edge * t[sizeOfPoint], * path[sizeOfPoint];

     static int aug[sizeOfPoint];

     int flow=;

     memcpy(t, e, sizeof e);

     memset(path, , sizeof path);

     memset(aug, , sizeof aug);

     aug[S]=inf;

     for (int u=S; ; )

     {

         if (u==T)

         {

             flow+=aug[T];

             for (edge * i=path[T];i;i=path[i->point])

             {

                 i->pair->flow-=aug[T], i->flow+=aug[T];

                 aug[i->point]-=aug[T];

                 if (!aug[i->point]) h[i->point]=-;

             }

             u=S;

         }

         edge *& i=t[u];

         for ( ;i && (!i->flow || h[u]!=h[i->point]+);i=i->next);

         if (i)

         {

             path[i->point]=i->pair; aug[i->point]=min(aug[u], i->flow);

             u=i->point; i=i->next;

         }

         else

         {

             if (u==S) break;

             u=path[u]->point;

         }

     }

     return flow;

 }

 inline int dinic()

 {

     int ret=, flow;

     while (bfs())

         while (flow=aug())

             ret+=flow;

     return ret;

 }

本傻调出翔系列