网络流24题之--魔术球问题

题面

其实没有范围

但是没有范围也没有关系。

声明:由于某些特殊原因,边i,j表示一条从i到j的有向边

求n根柱子最多几个球比较麻烦,但求n个球最少几根柱子会简单些。

显然j可以放在i上面的条件是i<j并且i+j=k2i+j=k^2,其中k是整数。

所以如果满足条件就连一条i,ji,j边。

然后最少用的柱子数就是最小路径覆盖数。

把每个点拆成两个点:入点XiX_i,出点YiY_i

对于每一对满足条件的 i,j i,j ,加一条XiX_iYjY_j的边。

则n-MAX就是答案,其中MAX为最大匹配数。

具体的证明:

一开始先把n个球全部放在不同的柱子上。

然后匹配的每一条边(Xi,Yj)(X_i,Y_j)表示把球j直接放在球i上面,就会少用一根柱子。

显然每个点不能被匹配两次,因为一个球不能有两个球都在它上面还紧挨着它,下面也一样。

然后显然少用的柱子数越多越好。

现在返回来考虑。

我们可以考虑每次加一个球,然后维护最大匹配。

如果在加上第k个球后只需要不超过n个柱子,但是k+1时就需要n+1个了,那么答案为k

维护最大匹配可以用匈牙利算法,也可以用网络流。

我写的匈牙利(似乎这样好输出方案些??)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
Author: CNYALI_LK
LANG: C++
PROG: 2765.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
int cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
putchar(end);
}
int beg[233333],to[1024244],lst[1024242],e;
int isss[1024242];
void add(int u,int v){
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
}
int visx[233333],is[233333];
int dfs(int x){
if(visx[x])return 0;
visx[x]=1;
for(int i=beg[x];i;i=lst[i])
if(!is[to[i]]){
is[to[i]]=x;
return 1;
}
else{
if(dfs(is[to[i]])){
is[to[i]]=x;
return 1;
}
}
return 0;
}
void fu(int x){
while(x){
printf("%d ",x);
visx[x]=1;
x=is[x];
}
putchar('\n');
}
int main(){
#ifdef cnyali_lk
freopen("2765.in","r",stdin);
freopen("2765.out","w",stdout);
#endif
int n;
n=read();
int m;
m=0;
for(int i=1;i<=256;++i)isss[i*i]=1;
while(n+1){
++m;
for(int j=1;j<m;++j)if(isss[m+j]){
add(m,j);
}
for(int i=1;i<=m;++i){
visx[i]=0;
}
--n+=dfs(m);
}
printf("%d\n",--m);
for(int i=1;i<=m;++i)visx[i]=0;
for(int i=1;i<=m;++i)if(!visx[i])fu(i);
return 0;
}
文章目录
  1. 1. 声明:由于某些特殊原因,边i,j表示一条从i到j的有向边
|