网络流24题-魔术球问题

#include<bits/stdc++.h>
using namespace std;
struct Node;
struct Edge;
const int maxn = 1e5;
struct Node{
    int id,level;
    Edge* head;
    bool visited;
}nodes[maxn*2+2],S,T;
struct Edge {
    int flow,capicity;
    Edge* reverseEdge,*next;
    Node *from,*to;
    Edge(Node* from,Node* to,int capa):from(from),to(to),capicity(capa),flow(0),next(from->head){};// 初始化flow=0
};

inline void add(Node* f,Node* t,int c){
    f->head = new Edge(f,t,c);
    t->head = new Edge(t,f,0); //反向边容量0
    f->head->reverseEdge = t->head;
    t->head->reverseEdge = f->head;
}
int n , m;

struct Dinic{
    bool makeLevelGraph(Node *s,Node *t,int n){
        for(int i = 1;i <= n;i++){
            nodes[i].level = nodes[i+maxn].level = 0;
        }
        t->level = 0;
        t->id = 999;
        s->level = 1;
        queue<Node*> q;
        q.push(s);
        while(!q.empty()){
            Node* h = q.front();
            q.pop();
            // cout<<"head->"<<h->id<<"\n";
            for(Edge* e = h->head;e;e=e->next){
                if(e->to->level == 0 && e->flow < e->capicity){//两个条件：没有level、可增广
                    e->to->level = h->level+1;
                    // cout<<e->to->id<<"<--"<<h->level+1<<"\n";
                    if(e->to == t){
                        return true;
                    }
                    else q.push(e->to);
                }
            }
        }

        return false;
    }

    int dfs(Node* s,Node* t ,int limit = INT_MAX){
        if(s == t) return limit;
        
        for(Edge* e = s->head;e;e=e->next){
            if(e->to->level == s->level+1 && e->capicity > e->flow){
                int flow = dfs(e->to,t,min(limit,e->capicity - e->flow));
                if(flow > 0 ){
                    e->flow += flow;
                    e->reverseEdge->flow -= flow;
                    return flow;
                }
            }
        }
        return 0;
    }

    int operator ()(Node* s,Node* t,int n){
        int ans = 0;
        while(makeLevelGraph(s,t,n)){
            int flow = 0;
            while(flow = dfs(s,t)>0) ans += flow;
        }
        return ans;
    }
}dinic;

void printPath(Node* v){
    cout<<v->id<<" ";
    v->visited = true;
    for(Edge* e = v->head;e;e=e->next){
        if(e->flow == e->capicity && !nodes[e->to->id].visited && e->to->id!=0){
            printPath(&nodes[e->to->id<<1-1]);
        }
    }
}
int s[maxn];
int main (){
    int n;
    cin>>n;
    int stick = 0,ball = 0;
    while(stick <= n){
        ball++;
        nodes[ball].id = nodes[ball+maxn].id = ball;
        add(&S,&nodes[ball],1);
        add(&nodes[ball+maxn],&T,1);
        for(int i = sqrt(ball)+1;i < sqrt(ball*2);i++){
            add(&nodes[(i*i-ball)],&nodes[ball+maxn],1); //
        }
        int flow = dinic(&S,&T,ball); //每次增广
        if(!flow){
            // cout<<ball<<'\n';
            s[++stick] = ball;
        }
    } 
    cout<<ball-1<<"\n";
    S.visited = true;
    T.visited = true;
    for(int i = 1;i <= n ;i++){
        printPath(&nodes[s[i]]);
        cout<<"\n";
    }
    // 淦 多种方案
    return 0;
}