「网络流 24 题」魔术球

「网络流 24 题」魔术球
题解：以样例中的答案11作解释，1-11之间可以连接一些边，比如1-3，1-8等等，我们从源点向Xi连边，从Yi向汇点连边，将连接的边变成Xu到Yv，那么我们的问题就变成了最小路径覆盖为n的图中最多允许存在多少个点？
题解：这样我们从小打到一次次尝试加点，同时根据网络流的性质，我们可以直接在残量网络上跑二分图匹配，然后问题就和最小路径覆盖一模一样了。
最小路径覆盖

#include <bits/stdc++.h>

const int MAXN = 100000,INF = 10000000;

using namespace std;

int n,e = 2,ans,mf,s,t;
int d[MAXN],cur[MAXN],head[MAXN];
bool vis[MAXN];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}

inline bool check(int u,int v){
    double sum = u+v;
    double sq = sqrt(sum);
    if(sum / sq == sq && sq == (int)sq) return true;
    else return false;
}

inline void init(){
    s = 0;t = 4000;
    ans = n;
    for(int i = 1;i <= ans;i++) addedge(s,i,1);
    for(int i = 1;i <= ans;i++) addedge(i+2000,t,1);
    
    for(int i = 1;i <= ans;i++)
        for(int j = i + 1;j <= ans;j++)
            if(check(i,j))
                addedge(i,j+2000,1);
    
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c - E.f,a))) > 0){
            E.f += f;
            edge[i^1].f += f;
            a -= f;
            flow += f;
            if(a == 0) break;
        }
    }
    return flow;
}

inline int max_flow()
{
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

void cut(int x){
    vis[x] = true;printf("%d ",x);
    for(int i = head[x];i;i = edge[i].next){
        node E = edge[i];
        if(1 <= E.v  - 2000&& E.v - 2000 <= ans&& !vis[E.v] && E.c == E.f){
            cut(E.v-2000);
        }
    } 
}

int main()
{
    scanf("%d",&n);
    init();mf = max_flow();
    while(ans - mf <= n){
        ans++;
        addedge(s,ans,1);
        addedge(ans+2000,t,1);
        for(int i = 1;i < ans;i++) if(check(i,ans)) addedge(i,ans+2000,1);
        mf += max_flow();
    }
    ans--;
    printf("%d\n",ans);
    
    for(int i = 1;i <= ans;i++){
        if(!vis[i]){
            cut(i);
            printf("\n");
        }
    }
    
    return 0;
}