M - Escape - HDU 3605 - （缩点+最大流SAP）

题目大意：2012世界末日来了，科学家发现了一些星球可以转移人口，不过有的人可以在一些星球上生存有的人不行，而且每个星球都有一定的承载量，现在想知道是否所有的人都可以安全转移呢？

输入：首先输入一个N和M，表示人数和星球数，接着输入N行，每行有M个01组成的数，0表示第Ni个人无法再Mj号星球上生存，1表示可以生存，最后一行是每个星球的最大承载量。

分析：刚看的时候是一道比较裸的最大流题目，只要求出来最大流是否等于总人口数就行了，不过人的数量貌似是有点多的，刚开始没有管那么多直接上了最大流，不过也果然TLE，后来借鉴了一下别人的想法，就是缩点，我们发现M的值是特别小的，最大只有10，这就意味着有很多人的状态是相同的（2^10）,所以可以把这些状态相同的人压缩到一起，这样最多也就1024个人了，大大缩减了复杂度，不过很不幸依然TLE！！！，好吧，认了，只能再去找一下sap的模板带入一下，刚开始随意找了一个模板套上，不过WA了，也不知道出了什么问题，，因为不了解SAP这东西，没办法，只能学一下SAP了，在网上找了一个很不错的演示。其实和dinic还是挺相似的，只不过这个只做了一次的DFS是从汇点到源点进行的分层，然后寻找可行弧（也就是下面有没有可以与之相连的边），如果没有可行弧，就修改他的层号，然后就这样一直找下去，直到源点的层号大于总点数或者出现断层就可以停止了。ps.生命不息，学习不止啊。

sap演示下载

下面是AC代码。

======================================================================================

#include<stdio.h>

#include<string.h>

#include<queue>

#include<math.h>

#include<algorithm>

using namespace std;

const int MAXN = ;

const int oo = 1e9+;

struct Edge{int u, v, flow, next;}edge[MAXN*];

int Head[MAXN], cnt;

int used[MAXN], cur[MAXN], Stack[MAXN];

int Layer[MAXN], gap[MAXN], cntv;///节点的总个数

void InIt()

{

    cnt = ;

    memset(Head, -, sizeof(Head));

    memset(used, , sizeof(used));

}

void AddEdge(int u, int v, int flow)

{

    edge[cnt].u = u;

    edge[cnt].v = v;

    edge[cnt].flow = flow;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

    edge[cnt].u = v;

    edge[cnt].v = u;

    edge[cnt].flow = ;

    edge[cnt].next = Head[v];

    Head[v] = cnt++;

}

void BFS(int End)

{

    memset(Layer, -, sizeof(Layer));

    memset(gap, , sizeof(gap));

    queue<int> Q;

    Q.push(End);

    Layer[End] = , gap[] = ;

    while(Q.size())

    {

        int u = Q.front();

        Q.pop();

        for(int j=Head[u]; j!=-; j=edge[j].next)

        {

            int v = edge[j].v;

            if(Layer[v] == -)

            {

                Layer[v] = Layer[u] + ;

                gap[Layer[v]]++;

                Q.push(v);

            }

        }

    }

}

int SAP(int start, int End)

{

    int j, top=, u = start, MaxFlow=;

    BFS(End);

    cntv = End;

    memcpy(cur, Head, sizeof(Head));

    while(Layer[start] < cntv)

    {///源点的层次小于总结点数,汇点是0层

        if(u == End)

        {

            int MinFlow = oo, location;///记录下最小流量边的位置，出栈时候用

            for(j=; j<top; j++)

            {

                int i = Stack[j];

                if(MinFlow > edge[i].flow)

                {

                    MinFlow = edge[i].flow;

                    location = j;

                }

            }

            for(j=; j<top; j++)

            {///所有的边减去路径上的最小流量

                int i = Stack[j];

                edge[i].flow -= MinFlow;

                edge[i^].flow += MinFlow;

            }

            MaxFlow += MinFlow;

            top = location;///退栈

            u = edge[Stack[top]].u;

        }

        else if(gap[Layer[u]-] == )

            break;///u所在的层下面的层没有了，出现了断层，也就没有了可行弧

        for(j=cur[u]; j!=-; j=edge[j].next)

        {///如果u有可行弧就停止

            if(Layer[u]==Layer[edge[j].v]+ && edge[j].flow)

                break;

        }

        if(j != -)

        {///找到了可行弧

            cur[u] = j;///u点的可行弧是j

            Stack[top++] = j;///记录下这条边

            u = edge[j].v;

        }

        else

        {///没有找到可行弧，修改标号

            int MinIndex = cntv;

            for(j=Head[u]; j!=-; j=edge[j].next)

            {///查找与u相连的最小的层是多少

                if(edge[j].flow && MinIndex > Layer[edge[j].v])

                {///记录下这条可行弧,下次可以直接访问这条边

                    MinIndex = Layer[edge[j].v];

                    cur[u] = j;

                }

            }

            gap[Layer[u]] -= ;///u改变层，所以u原来所在层的点数减去1

            Layer[u] = MinIndex + ;

            gap[Layer[u]] += ;

            if(u != start)

            {///返回上一层

                u = edge[Stack[--top]].u;

            }

        }

    }

    return MaxFlow;

}

int main()

{

    int N, M;

    while(scanf("%d%d", &N, &M) != EOF)

    {

        int i, j, u, Ni=pow(, M), start=Ni+M+, End=start+;

        char ch;

        InIt();

        for(i=; i<=N; i++)

        {

            u = ;

            for(j=; j<=M; j++)

            {

                while(ch = getchar(), ch ==' ' || ch == '\n');

                u = u* + ch-'';

            }

            used[u]++;///这种状态的人+1

        }

        for(i=; i<Ni; i++)

        {

            if(used[i])

            {

                AddEdge(start, i, used[i]);

            }

        }

        for(i=; i<=M; i++)

        {

            scanf("%d", &u);

            AddEdge(i+Ni, End, u);

        }

        for(i=; i<Ni; i++) if(used[i])

        {///如果这种状态有人

            u = i;

            for(j=M; j>; j--)

            {

                if(u&)

                {///最后一位是1

                    AddEdge(i, Ni+j, used[i]);

                }

                u = u >> ;

            }

        }

        int MaxFlow = SAP(start, End);

        if(MaxFlow == N)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return ;

}

巴特西

M - Escape - HDU 3605 - （缩点+最大流SAP）

最新文章

热门文章