luogu2765 魔术球问题网络流

题目大意：

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。

关键字：网络流拆点上下界二分查找

网络流：

想象拿柱子去串球，一个柱子就相当于一个流量为1的流。

拆点建图：

为保证每个球都能串在一个柱子上，将每个球拆成一条边，要求边内流量必须为1（即该边上下界都为1）。

若两球数字和为完全平方数，则将一球边的to节点连另一球边的from节点（注意球是按顺序放的，因此若a数字小于b数字，要么a连b，要么b连a，不能双向都连）。

为了满足网络流形式，“s”点向每个球边from点连边，每个球边to点向t点连边，容量为1。

因为柱子数量有限，因此将s点向“s”点连容量为柱子数量的边。

上下界：

根据上下界网络流处理办法，S点连每个球边to节点，每个球边from节点连T节点。之前的球边容量变为0，删去。t点向s点连容量∞边，即t，s点合并（合并点在代码中为orgT，"s"点为orgS）。

枚举：二分枚举球的数量直到得出答案。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cassert>

using namespace std;

//#define test

#define INF 0x3f3f3f3f

#define P(x) x*2+3

#define Q(x) x*2+4

#define arcP(x) (x-3)/2

#define arcQ(x) (x-4)/2

const int MAX_BALL = , MAX_NODE = MAX_BALL * , MAX_EDGE = , TOT_BALL = ;

struct Dinic

{

    struct Edge;

    struct Node;

    struct Node

    {

        int Id, Level;

        Edge* Head;

        Edge *DfsFrom;

        bool Deled;

        Node() { Deled = false; }

    };

    struct Edge

    {

        int Cap, OrgCap;

        Node *From, *To;

        Edge *Next, *Rev;

        Edge(int cap, Node *from, Node *to, Edge *next) :Cap(cap), OrgCap(cap), From(from), To(to), Next(next) {}

    };

    Node _nodes[MAX_NODE];

    Edge *_edges[MAX_EDGE];

    int _vCount, _eCount;

    Node *StartNode, *TargetNode;

    void Init(int sId, int tId, int vCount)

    {

        memset(_nodes, , sizeof(_nodes));

        memset(_edges, , sizeof(_edges));

        _eCount = ;

        _vCount = vCount;

        StartNode = sId + _nodes;

        TargetNode = tId + _nodes;

    }

    void Reuse(Node *cur)

    {

        cur->Deled = false;

        for (Edge *e = cur->Head; e; e = e->Next)

        {

            if (!e->To->Deled)

            {

                e->Cap = e->OrgCap;

                e->Rev->Cap = e->Rev->OrgCap;

            }

        }

    }

    void ReuseById(int id)

    {

        Reuse(id + _nodes);

    }

    Edge* AddEdge(Node *from, Node *to, int eCap)

    {

        assert(from != to);

        Edge *cur = _edges[++_eCount] = new Edge(eCap, from, to, from->Head);

        cur->From->Head = cur;

        return cur;

    }

    void DeleteNode(Node *cur)

    {

        cur->Deled = true;

        for (Edge *e = cur->Head; e; e = e->Next)

        {

            e->Cap = e->Rev->Cap = ;

        }

    }

    void DeleteById(int id)

    {

        DeleteNode(id + _nodes);

    }

    void Build(int uId, int vId, int eCap)

    {

        Node *u = uId + _nodes, *v = vId + _nodes;

        u->Id = uId;

        v->Id = vId;

        Edge *edge1 = AddEdge(u, v, eCap), *edge2 = AddEdge(v, u, );

        edge1->Rev = edge2;

        edge2->Rev = edge1;

    }

    struct NodeQueue

    {

        Node *q[MAX_NODE];

        int head, tail;

        void clear() { head = tail = ; }

        void push(Node *v) { q[tail++] = v; }

        Node* front() { return q[head]; }

        void pop() { head++; }

        bool empty() { return head == tail; }

    };

    bool Bfs()//常规，从源点构造

    {

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

            _nodes[i].Level = ;

        static NodeQueue q;

        q.clear();

        StartNode->Level = ;

        q.push(StartNode);

        while (!q.empty())

        {

            Node *u = q.front();

            q.pop();

            for (Edge *e = u->Head; e; e = e->Next)

            {

                assert(e->Cap >= );

                if (!e->To->Level && e->Cap)

                {

                    e->To->Level = u->Level + ;

                    q.push(e->To);

                }

            }

        }

        return TargetNode->Level;//遗忘点

    }

    int Dfs(Node *cur, int limit)

    {

        if (cur == TargetNode)

            return limit;

        if (limit == )

            return ;

        int curTake = ;

        for (Edge *e = cur->DfsFrom; e; cur->DfsFrom = e = e->Next)

        {

            if (e->To->Level == cur->Level +  && e->Cap)

            {

                int nextTake = Dfs(e->To, min(limit - curTake, e->Cap));

                e->Cap -= nextTake;

                e->Rev->Cap += nextTake;

                curTake += nextTake;

            }

            if (limit - curTake == )

                break;

            //assert(e->Cap == 0);

        }

        return curTake;

    }

    int Proceed()

    {

        int ans = ;

        while (Bfs())

        {

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

                _nodes[i].DfsFrom = _nodes[i].Head;

            ans += Dfs(StartNode, INF);

#ifdef test

            printf("ans=%d\n", ans);

#endif

        }

        //printf("ans %d\n", ans);

        return ans;

    }

}g;

Dinic::Edge *ts;

bool IsSquare(int x)

{

    int a = floor(sqrt(x) + 0.5);

    return a*a == x;

}

bool Judge(int ballCnt)

{

    //printf("ballCnt %d\n", ballCnt);

    g._vCount = ballCnt *  + ;

    ts->Cap = ts->OrgCap;

    ts->Rev->Cap = ts->Rev->OrgCap;

    for (int ball = ballCnt + ; ball <= TOT_BALL; ball++)

    {

        g.DeleteById(P(ball));

        g.DeleteById(Q(ball));

    }

    for (int ball = ; ball <= ballCnt; ball++)

    {

        g.ReuseById(P(ball));

        g.ReuseById(Q(ball));

    }

    return g.Proceed() == ballCnt;

}

int Bsearch(int maxL, int maxR)

{

    int l = maxL, r = maxR, ans = -;

    while (l <= r)

    {

        int mid = (l + r) / ;

        if (Judge(mid))

            l = (ans = mid) + ;

        else

            r = mid - ;

    }

    return ans;

}

void InitBuild(int totPole)

{

    int sId = , tId = , orgS = , orgT = ;

    g.Init(sId, tId, );

    g.Build(orgT, orgS, totPole);

    ts = g._edges[g._eCount - ];

    for (int ballNum = ; ballNum <= TOT_BALL; ballNum++)

    {

        g._vCount += ;

        g.Build(sId, Q(ballNum), );

        g.Build(P(ballNum), tId, );

        g.Build(orgS, P(ballNum), );

        g.Build(Q(ballNum), orgT, );

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

            if (IsSquare(i + ballNum))

                g.Build(Q(i), P(ballNum), );

    }

}

void Print(int ballNum)

{

    static bool Vis[MAX_BALL];

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

    {

        if (Vis[i])

            continue;

        Dinic::Node *p = P(i) + g._nodes, *q = Q(i) + g._nodes;

        bool stop = false;

        while (!stop)

        {

            Vis[arcP(p->Id)] = true;

            printf("%d ", arcP(p->Id));

            stop = true;

            for (Dinic::Edge *e = q->Head; e; e = e->Next)

            {

                if (arcP(e->To->Id) <= ballNum)

                    //printf("print %d' - %d cap %d\n", arcQ(q->Id), arcP(e->To->Id), e->Cap);

                    if (!e->Cap &&  <= arcP(e->To->Id) && arcP(e->To->Id) <= ballNum && !Vis[arcP(e->To->Id)] && !e->To->Deled)

                    {

                        stop = false;

                        p = e->To;

                        q = Q(arcP(p->Id)) + g._nodes;

                        break;

                    }

            }

        }

        printf("\n");

    }

}

int main()

{

#ifdef _DEBUG

    freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

    int totPole;

    scanf("%d", &totPole);

    InitBuild(totPole);

    int ballNum = Bsearch(, TOT_BALL);

    printf("%d\n", ballNum);

    Judge(ballNum);

    Print(ballNum);

    return ;

}

巴特西

luogu2765 魔术球问题网络流

最新文章

热门文章

巴特西

luogu2765 魔术球问题 网络流

最新文章

热门文章

luogu2765 魔术球问题网络流