P2765魔术球问题（网络流，隐式图构造）

P2765 魔术球问题

这道题的思路实在是太罕见了&＃xff0c;所以发一篇blog

从某一新放入的球开始看起

1.放入原来的柱子上

2.放入新的柱子

并将每个点进行拆点&＃xff0c;然后将可以组成平方数的两个树相连&＃xff0c;在每次跑网络流的时候记录流的流向即可&＃xff0c;如果流量为0&＃xff0c;则表明1行不通&＃xff0c;只能新来第一个柱子

#include
#include
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re int
#define void inline void
#define eps 1e-5
//#define mod 1e9&＃43;7
#define ls(p) p<<1
#define rs(p) p<<1|1
//#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
#define unordered_map map
//#define __int128 long long
using namespace std;
using namespace __gnu_pbds;
const int M&＃61;1e5&＃43;5;
const int mod&＃61;1e9;
const int N&＃61;2e6&＃43;5;
int n,s,t&＃61;100005;
int first[N],p,all;
int nxt[N],v[N];
namespace GP
{struct node{int ver,edge,next;}e[N];int tot&＃61;1,head[N];int d[N],gap[N];void add(int x,int y,int z){e[&＃43;&＃43;tot].ver&＃61;y;e[tot].edge&＃61;z;e[tot].next&＃61;head[x];head[x]&＃61;tot;}void addedge(int x,int y,int z){add(x,y,z);add(y,x,0);}void bfs(){int z&＃61;rs(p);
// printf("%d\n",rs(p));for(re i&＃61;0;i<&＃61;z;i&＃43;&＃43;) gap[i]&＃61;d[i]&＃61;0;
// puts("sad");queue < int > q;q.push(t),d[t]&＃61;gap[1]&＃61;1;
// cout<<"sdafd"<while(q.size()){int x&＃61;q.front();q.pop();
// cout<for(re i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(d[y]) continue;d[y]&＃61;d[x]&＃43;1;gap[d[y]]&＃43;&＃43;;q.push(y);}}}int dfs(int x,int flow){if(x&＃61;&＃61;t) return flow;int rest&＃61;0;for(re i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;int z&＃61;e[i].edge;if(!z||d[x]!&＃61;d[y]&＃43;1) continue;int k&＃61;dfs(y,min(z,flow-rest));if(k<&＃61;0) continue;e[i].edge-&＃61;k;e[i^1].edge&＃43;&＃61;k;rest&＃43;&＃61;k;nxt[x/2]&＃61;y/2;if(rest&＃61;&＃61;flow) return rest;}if(--gap[d[x]]&＃61;&＃61;0) d[s]&＃61;2*t&＃43;1;&＃43;&＃43;gap[&＃43;&＃43;d[x]];return rest;}int isap(){int maxflow&＃61;0;bfs();while(d[s]<&＃61;2*t) maxflow&＃43;&＃61;dfs(s,1e9);return maxflow;}
}
void solve()
{cin>>n;while(all<&＃61;n){p&＃43;&＃43;;GP::addedge(s,ls(p),1);GP::addedge(rs(p),t,1);
// cout<for(re i&＃61;sqrt(p)&＃43;1;i*i<ls(p);i&＃43;&＃43;){
// cout<GP::addedge(ls(i*i-p),rs(p),1);}
// puts("salj");int flow&＃61;GP::isap();
// cout<<"flow: "<if(!flow) first[&＃43;&＃43;all]&＃61;p;}printf("%d\n",p-1);for(re x&＃61;1;x<&＃61;n;x&＃43;&＃43;,puts("")) if(!v[first[x]]){for(re i&＃61;first[x];i&&i!&＃61;(t/2);i&＃61;nxt[i]) printf("%d ",i);}
}
signed main()
{
// fflush(stdout);
// srand(102321547);
// freopen("D.in", "r", stdin);
// freopen("D2.out", "w", stdout);
// freopen("9.out", "w", stdout);int T&＃61;1;
// cin>>T;for(re index&＃61;1;index<&＃61;T;index&＃43;&＃43;){
// printf("Case #%d:\n",index);solve();
// puts("");}return 0;
}
/*2
3 4 2 2
0000
0011
0000
1 4
2 4
3 4 2 2
0000
0011
0000
3 4
2 41
3 4 2 2
0000
1111
0000
1 4
2 42
3 4 2 2
0000
1111
0000
1 4
2 4
3 4 2 2
0000
0011
0000
3 4
2 4*/