题目大意：
假设有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 = 2510, MAX_NODE = MAX_BALL * 3, MAX_EDGE = 50000, TOT_BALL = 2500; 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, 0, sizeof(_nodes)); memset(_edges, 0, sizeof(_edges)); _eCount = 0; _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 = 0; } } 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, 0); edge1->Rev = edge2; edge2->Rev = edge1; } struct NodeQueue { Node *q[MAX_NODE]; int head, tail; void clear() { head = tail = 0; } 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 = 1; i <= _vCount; i++) _nodes[i].Level = 0; static NodeQueue q; q.clear(); StartNode->Level = 1; q.push(StartNode); while (!q.empty()) { Node *u = q.front(); q.pop(); for (Edge *e = u->Head; e; e = e->Next) { assert(e->Cap >= 0); if (!e->To->Level && e->Cap) { e->To->Level = u->Level + 1; q.push(e->To); } } } return TargetNode->Level;//遗忘点 } int Dfs(Node *cur, int limit) { if (cur == TargetNode) return limit; if (limit == 0) return 0; int curTake = 0; for (Edge *e = cur->DfsFrom; e; cur->DfsFrom = e = e->Next) { if (e->To->Level == cur->Level + 1 && e->Cap) { int nextTake = Dfs(e->To, min(limit - curTake, e->Cap)); e->Cap -= nextTake; e->Rev->Cap += nextTake; curTake += nextTake; } if (limit - curTake == 0) break; //assert(e->Cap == 0); } return curTake; } int Proceed() { int ans = 0; while (Bfs()) { for (int i = 0; i <= _vCount; i++) _nodes[i].DfsFrom = _nodes[i].Head; ans += Dfs(StartNode, INF); #ifdef test printf("ans=%d ", ans); #endif } //printf("ans %d ", 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 ", ballCnt); g._vCount = ballCnt * 2 + 4; ts->Cap = ts->OrgCap; ts->Rev->Cap = ts->Rev->OrgCap; for (int ball = ballCnt + 1; ball <= TOT_BALL; ball++) { g.DeleteById(P(ball)); g.DeleteById(Q(ball)); } for (int ball = 1; 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 = -1; while (l <= r) { int mid = (l + r) / 2; if (Judge(mid)) l = (ans = mid) + 1; else r = mid - 1; } return ans; } void InitBuild(int totPole) { int sId = 1, tId = 2, orgS = 3, orgT = 4; g.Init(sId, tId, 4); g.Build(orgT, orgS, totPole); ts = g._edges[g._eCount - 1]; for (int ballNum = 1; ballNum <= TOT_BALL; ballNum++) { g._vCount += 2; g.Build(sId, Q(ballNum), 1); g.Build(P(ballNum), tId, 1); g.Build(orgS, P(ballNum), 1); g.Build(Q(ballNum), orgT, 1); for (int i = 1; i < ballNum; i++) if (IsSquare(i + ballNum)) g.Build(Q(i), P(ballNum), 1); } } void Print(int ballNum) { static bool Vis[MAX_BALL]; for (int i = 1; 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 ", arcQ(q->Id), arcP(e->To->Id), e->Cap); if (!e->Cap && 1 <= 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(" "); } } int main() { #ifdef _DEBUG freopen("c:\noi\source\input.txt", "r", stdin); #endif int totPole; scanf("%d", &totPole); InitBuild(totPole); int ballNum = Bsearch(1, TOT_BALL); printf("%d ", ballNum); Judge(ballNum); Print(ballNum); return 0; }