最小路径覆盖模型，模型解法见 我上一篇BLOG：
https://blog.csdn.net/bjfu170203101/article/details/108956695
这题难点在于不知道点数，即不知道改用多少小球，枚举的话，每次重新跑dinic显然会T.
我们有两种方法解决这道题：
方法一：
打表找规律，找出每个n对应的小球的个数，只跑一遍dinic就行。
网络流的最坏复杂度是n^2*m , 但实际跑随机数据时(非完全图，边和点同一数量级)，效率很高，我们可以把它看成线性的复杂度。。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 40000+7; const int N = 4000+7; struct Dinic{ //N个点，M条边 //add建双向边，然后D.gao ,最后输出maxflow #define inf 0x3f3f3f3f ll maxflow;int s,t,n; int v[N],pre[N],d[N],now[N]; ll incf[N]; int head[N],cnt=1; struct EDGE{int to,nxt;ll w;}ee[M*2]; inline void AD(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} inline void add(int x,int y,ll w){AD(x,y,w);AD(y,x,0);} inline bool bfs()//在残量网络上构造分层图 { memset(d,0,sizeof(d)); queue<int>q; q.push(s);d[s]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; if(w&&!d[y]) { q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } } return false; } inline int dinic(int x,int flow) { if(x==t)return flow; ll rest = flow,k; for(int i=now[x];i&&rest;i=ee[i].nxt) { int y=ee[i].to;ll w= ee[i].w; now[x]=i; if(w&&d[y]==d[x]+1) { k=dinic(y,min(rest,w)); if(!k)d[y]=0;//剪枝，去掉增广完毕的点 ee[i].w-=k; ee[i^1].w+=k; rest-=k; } } return flow - rest; } inline void gao() { int flow=0; while(bfs()) { for(int i=0;i<=n;i++)now[i]=head[i]; while(flow=dinic(s,inf))maxflow+=flow; } } inline void init(int nn,int S,int T) { cnt=1;maxflow=0; for(int i=0;i<=n;i++)head[i]=0; s=S,t=T,n=nn; } }D; //求解二分图匹配问题时的复杂度是：m*sqrt(n)的 struct node{ int x,y,id; }p[M];//记录每条边 x -> y 反向边的编号 (cnt) int fa[N]; int gt(int x){ if(fa[x]==x)return x; return fa[x]=gt(fa[x]); } vector<int>G[M]; int n,s,t; bool gao(int nm){ s=2*nm+1,t=2*nm+2; int N = 2*nm+2; D.init(N,s,t); int sz=0; for(int j=1;j<=nm;j++){ for(auto y:G[j]){ if(y>nm)break; D.add(j,y+nm,1); p[++sz]=node{j,y,D.cnt}; // cout<<" = "<<j<<" -> "<<y<<" "<<endl; } }//cout<<sz<<" -- - ----------------"<<endl; for(int j=1;j<=nm;j++)D.add(s,j,1),D.add(j+nm,t,1); D.gao(); //if(nm-D.maxflow!=n)return false; cout<<nm<<endl; for(int i=1;i<=nm;i++)fa[i]=i; for(int i=1;i<=sz;i++){ if(D.ee[p[i].id].w){//这条边的反向边有流量即改边被最大流选中 //存在一条边 ： p[i].x -> p[i].y 即把与x相连的 和 与y相连的点集 合并 //由于求得的是不相交路径，每个点最多一个入边一个出边，所以最多往前合并一次，往后合并一次 //cout<<" = == = "<<p[i].x<<" "<<p[i].y<<endl; int gx=gt(p[i].x),gy=gt(p[i].y); if(gx!=gy)fa[gx]=gy; } } for(int i=1;i<=nm;i++){ bool flag=false; for(int j=1;j<=nm;j++){ if(gt(j)==i)cout<<j<<" ",flag=true; } if(flag)cout<<endl; } return true; } int c[100]; int main() { ios::sync_with_stdio(false); cin.tie(0); for(int i=1;i<=2000;i++) for(int j=i+1;j<=2000;j++){ int tp=i+j; if((int)sqrt(tp)*(int)sqrt(tp)==tp){ G[i].push_back(j); } } /* 打表发现 ： n=1，2，3，4，……时；球的数量为： 1,3,7,11,17,23,31 差分数组：2,4,4,6,6,8,8,………… */ cin>>n; c[1]=1;c[2]=3; int cz=4; for(int i=4;i<=n+2;i+=2){ c[i-1]=c[i-2]+cz; c[i]=c[i-1]+cz; cz+=2; } // cout<<c[n]<<endl; gao(c[n]); return 0; }
