[杂题] SPOJ744
发表评论30次阅读2008.01.04 20:45 作者：Felicia 编辑
[阅读更多]
这个题目是Sherlock推荐我做的。
题目意思是给一个长度为n（n <= 100000）的序列，里面的数满足1 <= a[i] <= n。要找一个最长的连续子串，使得这个子串是1..k的一个排列。
昨天晚上mmd想了个n^(3/2)的算法，今天Sherlock想了个nlogn的算法。我一直在考虑有没有O(n)的算法。我觉得应该有的。
今天晚上吃饭的时候忽然想出来了。回来写了果然AC。
下面是我的算法：
注意到满足题目要求的序列必有如下性质：
- 最大值等于长度
- 必含1
- 序列和为k * (k + 1) / 2
- 序列内元素不重复
如果一个序列同时满足性质3，4，那么一定符合题目要求。
于是如果做了O(n)的预处理，可以用O(1)的时间验证某序列是否满足题目要求。
然后我的算法就顺理成章了：
- 预处理s[i]，为序列的部分和
- 预处理rl[i]，为从i开始往右，最长的不重复序列的末端的下标
- 预处理m[i]，为从i开始，到i右边的第一个1（或者最右端），这一段数的最大值。
- 枚举左端点lp，则lp到其右边的第一个1（或者最右端）中的最大值为m[lp]。把m[lp]作为序列长度，则序列的右端点为lp + m[lp] – 1。利用s[i]和rl[i]数组可以验证这段序列是否满足题目要求，若满足，就更新最优解。
- 把输入序列反过来，重复步骤1－4。
以上每步的时间复杂度都是O(n)，故算法总的时间复杂度也是O(n)。
下面是我的代码
下载: spoj744.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2008-1-4 18:06:14
File Name: spoj744.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 100010;
int n;
int a[maxn];
int s[maxn];
int rl[maxn];
int hash[maxn];
int m[maxn];
int calc()
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = a[i] + s[i - 1];
memset(hash, 0, sizeof(hash));
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && hash[a[j]] == 0)
hash[a[j++]] = 1;
rl[i] = j - 1;
hash[a[i]] = 0;
}
for (int i = n; i >= 1; i--)
if (a[i] == 1)
m[i] = 1;
else if (i == n)
m[i] = a[i];
else
m[i] = max(m[i + 1], a[i]);
int ret = 0;
for (int i = 1; i <= n; i++)
if (rl[i] >= i + m[i] - 1 && s[i + m[i] - 1] - s[i - 1] == m[i] * (m[i] + 1) / 2)
ret >?= m[i];
return ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = calc();
reverse(a + 1, a + n + 1);
ans >?= calc();
printf("%d\n", ans);
return 0;
}
Author: WHU_GCC
Created Time: 2008-1-4 18:06:14
File Name: spoj744.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 100010;
int n;
int a[maxn];
int s[maxn];
int rl[maxn];
int hash[maxn];
int m[maxn];
int calc()
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = a[i] + s[i - 1];
memset(hash, 0, sizeof(hash));
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && hash[a[j]] == 0)
hash[a[j++]] = 1;
rl[i] = j - 1;
hash[a[i]] = 0;
}
for (int i = n; i >= 1; i--)
if (a[i] == 1)
m[i] = 1;
else if (i == n)
m[i] = a[i];
else
m[i] = max(m[i + 1], a[i]);
int ret = 0;
for (int i = 1; i <= n; i++)
if (rl[i] >= i + m[i] - 1 && s[i + m[i] - 1] - s[i - 1] == m[i] * (m[i] + 1) / 2)
ret >?= m[i];
return ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = calc();
reverse(a + 1, a + n + 1);
ans >?= calc();
printf("%d\n", ans);
return 0;
}
[TopCoder] SRM371 Div1
发表评论27次阅读2007.10.14 20:41 作者：Felicia 编辑
[阅读更多]
昨晚12点SRM。我和Sherlock玩命了一把，在机房睡了觉。在此感谢小金鱼的毯子：）
因为上次做到蓝名了，这次就能做Div1。以前都没有做过Div1的题目，赛前又听说比较难，心里就没底。比赛开始后看了250分的题，数据不大，按照ACM的规则，是可以模拟的。于是我就写了个模拟，一步一步走的那种，中间出了很多错，包括坐标系错误，RE，还有各种乱七八糟的就是不过样例。越做越郁闷……忽然突发奇想，发现可以用数学方法解决，果然很快又不会错。然后是500分的题。瞬秒，直接一个KM算法上去了。1000分的题没时间写了，因为受250的拖累……
最后结果是117 + 440。今天看一下rating，加了一点，有1494。不过还是没有达到wywcgs大牛的期望，差一点黄名。
要是第一题快些就好了
下次继续努力！
[计算几何] pku3391 平面欧几里得最小生成树
发表评论98次阅读2007.09.28 20:17 作者：Felicia 编辑
[阅读更多]
问题是求平面欧几里得最小生成树的第n – k小边。
平面欧几里德最小生成树是经典问题，可以做到O(nlogn)。具体做法是先对平面点进行三角剖分，时间复杂度是O(nlogn)，三角剖分的边就是可能的在最小生成树的边。因为是平面图，所以有O(n)条边，在其上应用 Kruscal 算法即可。
下面是我的代码
下载: pku3391.cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define TRUE 1
#define FALSE 0
#define Vector(p1, p2, u, v) (u = p2->x - p1->x, v = p2->y - p1->y)
#define Cross_product_2v(u1, v1, u2, v2) (u1 * v2 - v1 * u2)
#define Cross_product_3p(p1, p2, p3) ((p2->x - p1->x) * (p3->y - p1->y) - (p2->y - p1->y) * (p3->x - p1->x))
#define Dot_product_2v(u1, v1, u2, v2) (u1 * u2 + v1 * v2)
#define Org(e) ((e)->org)
#define Dest(e) ((e)->dest)
#define Onext(e) ((e)->onext)
#define Oprev(e) ((e)->oprev)
#define Dnext(e) ((e)->dnext)
#define Dprev(e) ((e)->dprev)
#define Other_point(e, p) ((e)->org == p ? (e)->dest : (e)->org)
#define Next(e, p) ((e)->org == p ? (e)->onext : (e)->dnext)
#define Prev(e, p) ((e)->org == p ? (e)->oprev : (e)->dprev)
#define Visited(p) ((p)->f)
#define Identical_refs(e1, e2) (e1 == e2)
typedef enum {right, left} side;
typedef double Real;
typedef int boolean;
typedef struct point point;
typedef struct edge edge;
struct point
{
Real x, y;
edge *entry_pt;
};
struct edge
{
point *org, *dest;
edge *onext, *oprev, *dnext, *dprev;
};
#define MAXV 1000001
#define MAXE 3000001
struct EDGE
{
int u, v;
double w;
};
EDGE E[MAXE], mst[MAXE];
int n, en, k;
double dist[MAXV];
int p[MAXV], d[MAXV];
void UFinit(int m)
{
int i;
for(i = 0; i < m; i++)
{
p[i] = i, d[i] = 0;
}
}
int UFfind(int x)
{
int i = x, j, k;
while(p[i] != i) i = p[i];
j = x;
while(p[j] != i)
{
k = p[j];
p[j] = i;
j = k;
}
return i;
}
void UFunion(int x, int y)
{
int i = UFfind(x), j = UFfind(y);
if(d[i] > d[j]) p[j] = i;
else
{
p[i] = j;
if(d[i] == d[j]) d[j]++;
}
}
bool cmp(const EDGE &e1, const EDGE &e2)
{
return e1.w < e2.w;
}
void kruskal(void)
{
if(k > n) k = n;
int i, kk;
sort(E, E + en, cmp);
UFinit(n);
for(i = 0, kk = 0; i < en && kk < n - 1; i++)
if(UFfind(E[i].u) != UFfind(E[i].v))
{
UFunion(E[i].u, E[i].v);
mst[kk++] = E[i];
}
printf("%d\n", int(ceil(mst[n - k - 1].w) + 0.00000001));
}
point *p_array;
static edge *e_array;
static edge **free_list_e;
static int n_free_e;
void alloc_memory(int n)
{
edge *e;
int i;
p_array = (point *)calloc(n, sizeof(point));
n_free_e = 3 * n;
e_array = e = (edge *)calloc(n_free_e, sizeof(edge));
free_list_e = (edge **)calloc(n_free_e, sizeof(edge *));
for(i = 0; i < n_free_e; i++, e++)
free_list_e[i] = e;
}
void free_memory(void)
{
free(p_array);
free(e_array);
free(free_list_e);
}
edge *get_edge(void)
{
if(n_free_e == 0)
printf("Out of memory for edges\n");
return (free_list_e[--n_free_e]);
}
void free_edge(edge *e)
{
free_list_e[n_free_e++] = e;
}
void splice(edge *a, edge *b, point *v)
{
edge *next;
if(Org(a) == v)
{
next = Onext(a);
Onext(a) = b;
}
else
{
next = Dnext(a);
Dnext(a) = b;
}
if(Org(next) == v)
Oprev(next) = b;
else
Dprev(next) = b;
if(Org(b) == v)
{
Onext(b) = next;
Oprev(b) = a;
}
else
{
Dnext(b) = next;
Dprev(b) = a;
}
}
edge *make_edge(point *u, point *v)
{
edge *e;
e = get_edge();
e->onext = e->oprev = e->dnext = e->dprev = e;
e->org = u;
e->dest = v;
if(u->entry_pt == NULL)
u->entry_pt = e;
if(v->entry_pt == NULL)
v->entry_pt = e;
return e;
}
edge *join(edge *a, point *u, edge *b, point *v, side s)
{
edge *e;
e = make_edge(u, v);
if(s == left)
{
if (Org(a) == u)
splice(Oprev(a), e, u);
else
splice(Dprev(a), e, u);
splice(b, e, v);
}
else
{
splice(a, e, u);
if(Org(b) == v)
splice(Oprev(b), e, v);
else
splice(Dprev(b), e, v);
}
return e;
}
void delete_edge(edge *e)
{
point *u, *v;
u = Org(e);
v = Dest(e);
if(u->entry_pt == e)
u->entry_pt = e->onext;
if(v->entry_pt == e)
v->entry_pt = e->dnext;
if(Org(e->onext) == u)
e->onext->oprev = e->oprev;
else
e->onext->dprev = e->oprev;
if(Org(e->oprev) == u)
e->oprev->onext = e->onext;
else
e->oprev->dnext = e->onext;
if(Org(e->dnext) == v)
e->dnext->oprev = e->dprev;
else
e->dnext->dprev = e->dprev;
if(Org(e->dprev) == v)
e->dprev->onext = e->dnext;
else
e->dprev->dnext = e->dnext;
free_edge(e);
}
double px[MAXV], py[MAXV];
void read_points()
{
int i = 0;
while (1)
{
int t1, t2;
scanf("%d", &t1);
px[i] = t1;
if (t1 == -1)
break;
scanf("%d", &t2);
py[i] = t2;
i++;
}
n = i;
}
static void print_edges(int n)
{
edge *e_start, *e;
point *u, *v;
int i;
for(i = 0; i < n; i++)
{
u = &p_array[i];
e_start = e = u->entry_pt;
do
{
v = Other_point(e, u);
if(u < v)
{
E[en].u = u - p_array, E[en].v = v - p_array;
E[en++].w = hypot(u->x - v->x, u->y - v->y);
}
e = Next(e, u);
}while(!Identical_refs(e, e_start));
}
}
void merge_sort(point *p[], point *p_temp[], int l, int r)
{
int i, j, k, m;
if(r - l > 0)
{
m = (r + l) / 2;
merge_sort(p, p_temp, l, m);
merge_sort(p, p_temp, m + 1, r);
for(i = m + 1; i > l; i--)
p_temp[i - 1] = p[i - 1];
for(j = m; j < r; j++)
p_temp[r + m - j] = p[j + 1];
for(k = l; k <= r; k++)
if(p_temp[i]->x < p_temp[j]->x)
{
p[k] = p_temp[i];
i = i + 1;
}
else if(p_temp[i]->x == p_temp[j]->x && p_temp[i]->y < p_temp[j]->y)
{
p[k] = p_temp[i];
i = i + 1;
}
else
{
p[k] = p_temp[j];
j = j - 1;
}
}
}
static void lower_tangent(edge *r_cw_l, point *s, edge *l_ccw_r, point *u, edge **l_lower, point **org_l_lower, edge **r_lower, point **org_r_lower)
{
edge *l, *r;
point *o_l, *o_r, *d_l, *d_r;
boolean finished;
l = r_cw_l;
r = l_ccw_r;
o_l = s;
d_l = Other_point(l, s);
o_r = u;
d_r = Other_point(r, u);
finished = FALSE;
while(!finished)
if(Cross_product_3p(o_l, d_l, o_r) > 0.0)
{
l = Prev(l, d_l);
o_l = d_l;
d_l = Other_point(l, o_l);
}
else if(Cross_product_3p(o_r, d_r, o_l) < 0.0)
{
r = Next(r, d_r);
o_r = d_r;
d_r = Other_point(r, o_r);
}
else
finished = TRUE;
*l_lower = l;
*r_lower = r;
*org_l_lower = o_l;
*org_r_lower = o_r;
}
static void merge(edge *r_cw_l, point *s, edge *l_ccw_r, point *u, edge **l_tangent)
{
edge *base, *l_cand, *r_cand;
point *org_base, *dest_base;
Real u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b;
Real u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b;
Real c_p_l_cand, c_p_r_cand;
Real d_p_l_cand, d_p_r_cand;
boolean above_l_cand, above_r_cand, above_next, above_prev;
point *dest_l_cand, *dest_r_cand;
Real cot_l_cand, cot_r_cand;
edge *l_lower, *r_lower;
point *org_r_lower, *org_l_lower;
lower_tangent(r_cw_l, s, l_ccw_r, u, &l_lower, &org_l_lower, &r_lower, &org_r_lower);
base = join(l_lower, org_l_lower, r_lower, org_r_lower, right);
org_base = org_l_lower;
dest_base = org_r_lower;
*l_tangent = base;
do
{
l_cand = Next(base, org_base);
r_cand = Prev(base, dest_base);
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
Vector(dest_l_cand, org_base, u_l_c_o_b, v_l_c_o_b);
Vector(dest_l_cand, dest_base, u_l_c_d_b, v_l_c_d_b);
Vector(dest_r_cand, org_base, u_r_c_o_b, v_r_c_o_b);
Vector(dest_r_cand, dest_base, u_r_c_d_b, v_r_c_d_b);
c_p_l_cand = Cross_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
c_p_r_cand = Cross_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
above_l_cand = c_p_l_cand > 0.0;
above_r_cand = c_p_r_cand > 0.0;
if(!above_l_cand && !above_r_cand)
break;
if(above_l_cand)
{
Real u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b;
Real c_p_next, d_p_next, cot_next;
edge *next;
point *dest_next;
d_p_l_cand = Dot_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
cot_l_cand = d_p_l_cand / c_p_l_cand;
do
{
next = Next(l_cand, org_base);
dest_next = Other_point(next, org_base);
Vector(dest_next, org_base, u_n_o_b, v_n_o_b);
Vector(dest_next, dest_base, u_n_d_b, v_n_d_b);
c_p_next = Cross_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
above_next = c_p_next > 0.0;
if(!above_next)
break;
d_p_next = Dot_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
cot_next = d_p_next / c_p_next;
if(cot_next > cot_l_cand)
break;
delete_edge(l_cand);
l_cand = next;
cot_l_cand = cot_next;
}while(TRUE);
}
if(above_r_cand)
{
Real u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b;
Real c_p_prev, d_p_prev, cot_prev;
edge *prev;
point *dest_prev;
d_p_r_cand = Dot_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
cot_r_cand = d_p_r_cand / c_p_r_cand;
do
{
prev = Prev(r_cand, dest_base);
dest_prev = Other_point(prev, dest_base);
Vector(dest_prev, org_base, u_p_o_b, v_p_o_b);
Vector(dest_prev, dest_base, u_p_d_b, v_p_d_b);
c_p_prev = Cross_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
above_prev = c_p_prev > 0.0;
if(!above_prev)
break;
d_p_prev = Dot_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
cot_prev = d_p_prev / c_p_prev;
if(cot_prev > cot_r_cand)
break;
delete_edge(r_cand);
r_cand = prev;
cot_r_cand = cot_prev;
}while(TRUE);
}
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
if(!above_l_cand || (above_l_cand && above_r_cand && cot_r_cand < cot_l_cand))
{
base = join(base, org_base, r_cand, dest_r_cand, right);
dest_base = dest_r_cand;
}
else
{
base = join(l_cand, dest_l_cand, base, dest_base, right);
org_base = dest_l_cand;
}
}while(TRUE);
}
void divide(point *p_sorted[], int l, int r, edge **l_ccw, edge **r_cw)
{
int n;
int split;
edge *l_ccw_l, *r_cw_l, *l_ccw_r, *r_cw_r, *l_tangent;
edge *a, *b, *c;
Real c_p;
n = r - l + 1;
if(n == 2)
{
*l_ccw = *r_cw = make_edge(p_sorted[l], p_sorted[r]);
}
else if(n == 3)
{
a = make_edge(p_sorted[l], p_sorted[l + 1]);
b = make_edge(p_sorted[l + 1], p_sorted[r]);
splice(a, b, p_sorted[l + 1]);
c_p = Cross_product_3p(p_sorted[l], p_sorted[l + 1], p_sorted[r]);
if(c_p > 0.0)
{
c = join(a, p_sorted[l], b, p_sorted[r], right);
*l_ccw = a;
*r_cw = b;
}
else if(c_p < 0.0)
{
c = join(a, p_sorted[l], b, p_sorted[r], left);
*l_ccw = c;
*r_cw = c;
}
else
{
*l_ccw = a;
*r_cw = b;
}
}
else if(n > 3)
{
split = (l + r) / 2;
divide(p_sorted, l, split, &l_ccw_l, &r_cw_l);
divide(p_sorted, split+1, r, &l_ccw_r, &r_cw_r);
merge(r_cw_l, p_sorted[split], l_ccw_r, p_sorted[split + 1], &l_tangent);
if(Org(l_tangent) == p_sorted[l])
l_ccw_l = l_tangent;
if(Dest(l_tangent) == p_sorted[r])
r_cw_r = l_tangent;
*l_ccw = l_ccw_l;
*r_cw = r_cw_r;
}
}
int main(void)
{
int ca;
for (scanf("%d", &ca); ca--;)
{
scanf("%d", &k);
edge *l_cw, *r_ccw;
int i;
point **p_sorted, **p_temp;
read_points();
if (k > n) k = n;
if (n == 1)
{
printf("0\n");
continue;
}
alloc_memory(n);
for (i = 0; i < n; i++)
{
p_array[i].x = px[i];
p_array[i].y = py[i];
}
for(i = 0; i < n; i++)
p_array[i].entry_pt = NULL;
p_sorted = (point **)malloc((unsigned)n * sizeof(point *));
p_temp = (point **)malloc((unsigned)n * sizeof(point *));
for(i = 0; i < n; i++)
p_sorted[i] = p_array + i;
merge_sort(p_sorted, p_temp, 0, n - 1);
free((char *)p_temp);
divide(p_sorted, 0, n - 1, &l_cw, &r_ccw);
free((char *)p_sorted);
en = 0;
print_edges(n);
kruskal();
free_memory();
}
return 0;
}
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define TRUE 1
#define FALSE 0
#define Vector(p1, p2, u, v) (u = p2->x - p1->x, v = p2->y - p1->y)
#define Cross_product_2v(u1, v1, u2, v2) (u1 * v2 - v1 * u2)
#define Cross_product_3p(p1, p2, p3) ((p2->x - p1->x) * (p3->y - p1->y) - (p2->y - p1->y) * (p3->x - p1->x))
#define Dot_product_2v(u1, v1, u2, v2) (u1 * u2 + v1 * v2)
#define Org(e) ((e)->org)
#define Dest(e) ((e)->dest)
#define Onext(e) ((e)->onext)
#define Oprev(e) ((e)->oprev)
#define Dnext(e) ((e)->dnext)
#define Dprev(e) ((e)->dprev)
#define Other_point(e, p) ((e)->org == p ? (e)->dest : (e)->org)
#define Next(e, p) ((e)->org == p ? (e)->onext : (e)->dnext)
#define Prev(e, p) ((e)->org == p ? (e)->oprev : (e)->dprev)
#define Visited(p) ((p)->f)
#define Identical_refs(e1, e2) (e1 == e2)
typedef enum {right, left} side;
typedef double Real;
typedef int boolean;
typedef struct point point;
typedef struct edge edge;
struct point
{
Real x, y;
edge *entry_pt;
};
struct edge
{
point *org, *dest;
edge *onext, *oprev, *dnext, *dprev;
};
#define MAXV 1000001
#define MAXE 3000001
struct EDGE
{
int u, v;
double w;
};
EDGE E[MAXE], mst[MAXE];
int n, en, k;
double dist[MAXV];
int p[MAXV], d[MAXV];
void UFinit(int m)
{
int i;
for(i = 0; i < m; i++)
{
p[i] = i, d[i] = 0;
}
}
int UFfind(int x)
{
int i = x, j, k;
while(p[i] != i) i = p[i];
j = x;
while(p[j] != i)
{
k = p[j];
p[j] = i;
j = k;
}
return i;
}
void UFunion(int x, int y)
{
int i = UFfind(x), j = UFfind(y);
if(d[i] > d[j]) p[j] = i;
else
{
p[i] = j;
if(d[i] == d[j]) d[j]++;
}
}
bool cmp(const EDGE &e1, const EDGE &e2)
{
return e1.w < e2.w;
}
void kruskal(void)
{
if(k > n) k = n;
int i, kk;
sort(E, E + en, cmp);
UFinit(n);
for(i = 0, kk = 0; i < en && kk < n - 1; i++)
if(UFfind(E[i].u) != UFfind(E[i].v))
{
UFunion(E[i].u, E[i].v);
mst[kk++] = E[i];
}
printf("%d\n", int(ceil(mst[n - k - 1].w) + 0.00000001));
}
point *p_array;
static edge *e_array;
static edge **free_list_e;
static int n_free_e;
void alloc_memory(int n)
{
edge *e;
int i;
p_array = (point *)calloc(n, sizeof(point));
n_free_e = 3 * n;
e_array = e = (edge *)calloc(n_free_e, sizeof(edge));
free_list_e = (edge **)calloc(n_free_e, sizeof(edge *));
for(i = 0; i < n_free_e; i++, e++)
free_list_e[i] = e;
}
void free_memory(void)
{
free(p_array);
free(e_array);
free(free_list_e);
}
edge *get_edge(void)
{
if(n_free_e == 0)
printf("Out of memory for edges\n");
return (free_list_e[--n_free_e]);
}
void free_edge(edge *e)
{
free_list_e[n_free_e++] = e;
}
void splice(edge *a, edge *b, point *v)
{
edge *next;
if(Org(a) == v)
{
next = Onext(a);
Onext(a) = b;
}
else
{
next = Dnext(a);
Dnext(a) = b;
}
if(Org(next) == v)
Oprev(next) = b;
else
Dprev(next) = b;
if(Org(b) == v)
{
Onext(b) = next;
Oprev(b) = a;
}
else
{
Dnext(b) = next;
Dprev(b) = a;
}
}
edge *make_edge(point *u, point *v)
{
edge *e;
e = get_edge();
e->onext = e->oprev = e->dnext = e->dprev = e;
e->org = u;
e->dest = v;
if(u->entry_pt == NULL)
u->entry_pt = e;
if(v->entry_pt == NULL)
v->entry_pt = e;
return e;
}
edge *join(edge *a, point *u, edge *b, point *v, side s)
{
edge *e;
e = make_edge(u, v);
if(s == left)
{
if (Org(a) == u)
splice(Oprev(a), e, u);
else
splice(Dprev(a), e, u);
splice(b, e, v);
}
else
{
splice(a, e, u);
if(Org(b) == v)
splice(Oprev(b), e, v);
else
splice(Dprev(b), e, v);
}
return e;
}
void delete_edge(edge *e)
{
point *u, *v;
u = Org(e);
v = Dest(e);
if(u->entry_pt == e)
u->entry_pt = e->onext;
if(v->entry_pt == e)
v->entry_pt = e->dnext;
if(Org(e->onext) == u)
e->onext->oprev = e->oprev;
else
e->onext->dprev = e->oprev;
if(Org(e->oprev) == u)
e->oprev->onext = e->onext;
else
e->oprev->dnext = e->onext;
if(Org(e->dnext) == v)
e->dnext->oprev = e->dprev;
else
e->dnext->dprev = e->dprev;
if(Org(e->dprev) == v)
e->dprev->onext = e->dnext;
else
e->dprev->dnext = e->dnext;
free_edge(e);
}
double px[MAXV], py[MAXV];
void read_points()
{
int i = 0;
while (1)
{
int t1, t2;
scanf("%d", &t1);
px[i] = t1;
if (t1 == -1)
break;
scanf("%d", &t2);
py[i] = t2;
i++;
}
n = i;
}
static void print_edges(int n)
{
edge *e_start, *e;
point *u, *v;
int i;
for(i = 0; i < n; i++)
{
u = &p_array[i];
e_start = e = u->entry_pt;
do
{
v = Other_point(e, u);
if(u < v)
{
E[en].u = u - p_array, E[en].v = v - p_array;
E[en++].w = hypot(u->x - v->x, u->y - v->y);
}
e = Next(e, u);
}while(!Identical_refs(e, e_start));
}
}
void merge_sort(point *p[], point *p_temp[], int l, int r)
{
int i, j, k, m;
if(r - l > 0)
{
m = (r + l) / 2;
merge_sort(p, p_temp, l, m);
merge_sort(p, p_temp, m + 1, r);
for(i = m + 1; i > l; i--)
p_temp[i - 1] = p[i - 1];
for(j = m; j < r; j++)
p_temp[r + m - j] = p[j + 1];
for(k = l; k <= r; k++)
if(p_temp[i]->x < p_temp[j]->x)
{
p[k] = p_temp[i];
i = i + 1;
}
else if(p_temp[i]->x == p_temp[j]->x && p_temp[i]->y < p_temp[j]->y)
{
p[k] = p_temp[i];
i = i + 1;
}
else
{
p[k] = p_temp[j];
j = j - 1;
}
}
}
static void lower_tangent(edge *r_cw_l, point *s, edge *l_ccw_r, point *u, edge **l_lower, point **org_l_lower, edge **r_lower, point **org_r_lower)
{
edge *l, *r;
point *o_l, *o_r, *d_l, *d_r;
boolean finished;
l = r_cw_l;
r = l_ccw_r;
o_l = s;
d_l = Other_point(l, s);
o_r = u;
d_r = Other_point(r, u);
finished = FALSE;
while(!finished)
if(Cross_product_3p(o_l, d_l, o_r) > 0.0)
{
l = Prev(l, d_l);
o_l = d_l;
d_l = Other_point(l, o_l);
}
else if(Cross_product_3p(o_r, d_r, o_l) < 0.0)
{
r = Next(r, d_r);
o_r = d_r;
d_r = Other_point(r, o_r);
}
else
finished = TRUE;
*l_lower = l;
*r_lower = r;
*org_l_lower = o_l;
*org_r_lower = o_r;
}
static void merge(edge *r_cw_l, point *s, edge *l_ccw_r, point *u, edge **l_tangent)
{
edge *base, *l_cand, *r_cand;
point *org_base, *dest_base;
Real u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b;
Real u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b;
Real c_p_l_cand, c_p_r_cand;
Real d_p_l_cand, d_p_r_cand;
boolean above_l_cand, above_r_cand, above_next, above_prev;
point *dest_l_cand, *dest_r_cand;
Real cot_l_cand, cot_r_cand;
edge *l_lower, *r_lower;
point *org_r_lower, *org_l_lower;
lower_tangent(r_cw_l, s, l_ccw_r, u, &l_lower, &org_l_lower, &r_lower, &org_r_lower);
base = join(l_lower, org_l_lower, r_lower, org_r_lower, right);
org_base = org_l_lower;
dest_base = org_r_lower;
*l_tangent = base;
do
{
l_cand = Next(base, org_base);
r_cand = Prev(base, dest_base);
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
Vector(dest_l_cand, org_base, u_l_c_o_b, v_l_c_o_b);
Vector(dest_l_cand, dest_base, u_l_c_d_b, v_l_c_d_b);
Vector(dest_r_cand, org_base, u_r_c_o_b, v_r_c_o_b);
Vector(dest_r_cand, dest_base, u_r_c_d_b, v_r_c_d_b);
c_p_l_cand = Cross_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
c_p_r_cand = Cross_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
above_l_cand = c_p_l_cand > 0.0;
above_r_cand = c_p_r_cand > 0.0;
if(!above_l_cand && !above_r_cand)
break;
if(above_l_cand)
{
Real u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b;
Real c_p_next, d_p_next, cot_next;
edge *next;
point *dest_next;
d_p_l_cand = Dot_product_2v(u_l_c_o_b, v_l_c_o_b, u_l_c_d_b, v_l_c_d_b);
cot_l_cand = d_p_l_cand / c_p_l_cand;
do
{
next = Next(l_cand, org_base);
dest_next = Other_point(next, org_base);
Vector(dest_next, org_base, u_n_o_b, v_n_o_b);
Vector(dest_next, dest_base, u_n_d_b, v_n_d_b);
c_p_next = Cross_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
above_next = c_p_next > 0.0;
if(!above_next)
break;
d_p_next = Dot_product_2v(u_n_o_b, v_n_o_b, u_n_d_b, v_n_d_b);
cot_next = d_p_next / c_p_next;
if(cot_next > cot_l_cand)
break;
delete_edge(l_cand);
l_cand = next;
cot_l_cand = cot_next;
}while(TRUE);
}
if(above_r_cand)
{
Real u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b;
Real c_p_prev, d_p_prev, cot_prev;
edge *prev;
point *dest_prev;
d_p_r_cand = Dot_product_2v(u_r_c_o_b, v_r_c_o_b, u_r_c_d_b, v_r_c_d_b);
cot_r_cand = d_p_r_cand / c_p_r_cand;
do
{
prev = Prev(r_cand, dest_base);
dest_prev = Other_point(prev, dest_base);
Vector(dest_prev, org_base, u_p_o_b, v_p_o_b);
Vector(dest_prev, dest_base, u_p_d_b, v_p_d_b);
c_p_prev = Cross_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
above_prev = c_p_prev > 0.0;
if(!above_prev)
break;
d_p_prev = Dot_product_2v(u_p_o_b, v_p_o_b, u_p_d_b, v_p_d_b);
cot_prev = d_p_prev / c_p_prev;
if(cot_prev > cot_r_cand)
break;
delete_edge(r_cand);
r_cand = prev;
cot_r_cand = cot_prev;
}while(TRUE);
}
dest_l_cand = Other_point(l_cand, org_base);
dest_r_cand = Other_point(r_cand, dest_base);
if(!above_l_cand || (above_l_cand && above_r_cand && cot_r_cand < cot_l_cand))
{
base = join(base, org_base, r_cand, dest_r_cand, right);
dest_base = dest_r_cand;
}
else
{
base = join(l_cand, dest_l_cand, base, dest_base, right);
org_base = dest_l_cand;
}
}while(TRUE);
}
void divide(point *p_sorted[], int l, int r, edge **l_ccw, edge **r_cw)
{
int n;
int split;
edge *l_ccw_l, *r_cw_l, *l_ccw_r, *r_cw_r, *l_tangent;
edge *a, *b, *c;
Real c_p;
n = r - l + 1;
if(n == 2)
{
*l_ccw = *r_cw = make_edge(p_sorted[l], p_sorted[r]);
}
else if(n == 3)
{
a = make_edge(p_sorted[l], p_sorted[l + 1]);
b = make_edge(p_sorted[l + 1], p_sorted[r]);
splice(a, b, p_sorted[l + 1]);
c_p = Cross_product_3p(p_sorted[l], p_sorted[l + 1], p_sorted[r]);
if(c_p > 0.0)
{
c = join(a, p_sorted[l], b, p_sorted[r], right);
*l_ccw = a;
*r_cw = b;
}
else if(c_p < 0.0)
{
c = join(a, p_sorted[l], b, p_sorted[r], left);
*l_ccw = c;
*r_cw = c;
}
else
{
*l_ccw = a;
*r_cw = b;
}
}
else if(n > 3)
{
split = (l + r) / 2;
divide(p_sorted, l, split, &l_ccw_l, &r_cw_l);
divide(p_sorted, split+1, r, &l_ccw_r, &r_cw_r);
merge(r_cw_l, p_sorted[split], l_ccw_r, p_sorted[split + 1], &l_tangent);
if(Org(l_tangent) == p_sorted[l])
l_ccw_l = l_tangent;
if(Dest(l_tangent) == p_sorted[r])
r_cw_r = l_tangent;
*l_ccw = l_ccw_l;
*r_cw = r_cw_r;
}
}
int main(void)
{
int ca;
for (scanf("%d", &ca); ca--;)
{
scanf("%d", &k);
edge *l_cw, *r_ccw;
int i;
point **p_sorted, **p_temp;
read_points();
if (k > n) k = n;
if (n == 1)
{
printf("0\n");
continue;
}
alloc_memory(n);
for (i = 0; i < n; i++)
{
p_array[i].x = px[i];
p_array[i].y = py[i];
}
for(i = 0; i < n; i++)
p_array[i].entry_pt = NULL;
p_sorted = (point **)malloc((unsigned)n * sizeof(point *));
p_temp = (point **)malloc((unsigned)n * sizeof(point *));
for(i = 0; i < n; i++)
p_sorted[i] = p_array + i;
merge_sort(p_sorted, p_temp, 0, n - 1);
free((char *)p_temp);
divide(p_sorted, 0, n - 1, &l_cw, &r_ccw);
free((char *)p_sorted);
en = 0;
print_edges(n);
kruskal();
free_memory();
}
return 0;
}
[计算几何] pku3384 半平面交的应用
发表评论80次阅读2007.09.23 16:19 作者：Felicia 编辑
[阅读更多]
强烈推荐此题。半平面交算法的一个应用。
具体做法是，把多边形的每条边向内平移r单位长度，用这些线段所在直线和原多边形作半平面交，得到的区域就是半径为r的圆放入多边形的可行域。可以证明这个区域一定是凸的，或者退化为一条线段，或一个点。那么，我们就可以在这个区域上求最远点对啦。
我的做法是O(n2)的。应该存在O(nlogn)的做法，因为都是凸多边形，每次半平面交只有最多两个交点，可二分，而最后的求最远点对可以旋转卡壳。比赛的时候时间少，就写了个暴力O(n2)的。
下面是我的代码
下载: pku3384.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-9-23 12:02:01
File Name: pku3384.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
const double eps = 1e-10;
const int maxn = 200;
struct point
{
double x, y;
};
struct cp
{
int n;
point p[maxn];
};
double dist(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
point intersectL(double a1, double b1, double c1, double a2, double b2, double c2)
{
point ret;
ret.y = (a1 * c2 - c1 * a2) / (b1 * a2 - a1 * b2);
if (fabs(a2) < eps)
ret.x = -(b1 * ret.y + c1) / a1;
else
ret.x = -(b2 * ret.y + c2) / a2;
return ret;
}
bool isEqual(point inpA, point inpB)
{
return (fabs(inpA.x - inpB.x) < eps && fabs(inpA.y - inpB.y) < eps);
}
double Cross(point inpA, point inpB, point inpC)
{
return (inpB.x - inpA.x) * (inpC.y - inpA.y) - (inpC.x - inpA.x) * (inpB.y - inpA.y);
}
void get_line(point inpA, point inpB, double &a1, double &b1, double &c1)
{
a1 = inpB.y - inpA.y;
b1 = inpA.x - inpB.x;
c1 = inpA.y * (inpB.x - inpA.x) - inpA.x * (inpB.y - inpA.y);
}
cp cut(point inpA, point inpB, cp incp)
{
cp ret;
point cross;
int i, j;
double t1, t2;
double a1, b1, c1, a2, b2, c2;
ret.n = 0;
for (i = 0; i < incp.n; i++)
{
j = i + 1;
t1 = Cross(inpA, inpB, incp.p[i]);
t2 = Cross(inpA, inpB, incp.p[j]);
if (t1 < eps && t2 < eps)
{
ret.p[ret.n++] = incp.p[i];
ret.p[ret.n++] = incp.p[j];
}
else if (t1 > eps && t2 > eps)
continue;
else
{
get_line(inpA, inpB, a1, b1, c1);
get_line(incp.p[i], incp.p[j], a2, b2, c2);
cross = intersectL(a1, b1, c1, a2, b2, c2);
if (t1 < eps)
{
ret.p[ret.n++] = incp.p[i];
ret.p[ret.n++] = cross;
}
else
{
ret.p[ret.n++] = cross;
ret.p[ret.n++] = incp.p[j];
}
}
}
if (ret.n == 0)
return ret;
for (i = 1, j = 1; i < ret.n; i++)
if (!isEqual(ret.p[i - 1], ret.p[i]))
ret.p[j++] = ret.p[i];
ret.n = j;
if (ret.n != 1 && isEqual(ret.p[ret.n - 1], ret.p[0]))
ret.n--;
ret.p[ret.n] = ret.p[0];
return ret;
}
int main()
{
int n, r;
cp input, ret;
scanf("%d%d", &n, &r);
input.n = n;
for (int i = 0; i < n; i++)
scanf("%lf%lf", &input.p[i].x, &input.p[i].y);
input.p[n] = input.p[0];
ret = input;
for (int i = 0; i < n; i++)
{
point ta, tb, tt;
tt.x = input.p[i + 1].y - input.p[i].y;
tt.y = input.p[i].x - input.p[i + 1].x;
double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);
tt.x = tt.x * k;
tt.y = tt.y * k;
ta.x = input.p[i].x + tt.x;
ta.y = input.p[i].y + tt.y;
tb.x = input.p[i + 1].x + tt.x;
tb.y = input.p[i + 1].y + tt.y;
ret = cut(ta, tb, ret);
}
double ans = -1;
double ans_x1, ans_y1, ans_x2, ans_y2;
for (int i = 0; i < ret.n; i++)
for (int j = 0; j < ret.n; j++)
{
double t = dist(ret.p[i], ret.p[j]);
if (t > ans)
{
ans = t;
ans_x1 = ret.p[i].x;
ans_y1 = ret.p[i].y;
ans_x2 = ret.p[j].x;
ans_y2 = ret.p[j].y;
}
}
printf("%.4lf %.4lf %.4lf %.4lf\n", ans_x1, ans_y1, ans_x2, ans_y2);
return 0;
}
Author: WHU_GCC
Created Time: 2007-9-23 12:02:01
File Name: pku3384.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
const double eps = 1e-10;
const int maxn = 200;
struct point
{
double x, y;
};
struct cp
{
int n;
point p[maxn];
};
double dist(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
point intersectL(double a1, double b1, double c1, double a2, double b2, double c2)
{
point ret;
ret.y = (a1 * c2 - c1 * a2) / (b1 * a2 - a1 * b2);
if (fabs(a2) < eps)
ret.x = -(b1 * ret.y + c1) / a1;
else
ret.x = -(b2 * ret.y + c2) / a2;
return ret;
}
bool isEqual(point inpA, point inpB)
{
return (fabs(inpA.x - inpB.x) < eps && fabs(inpA.y - inpB.y) < eps);
}
double Cross(point inpA, point inpB, point inpC)
{
return (inpB.x - inpA.x) * (inpC.y - inpA.y) - (inpC.x - inpA.x) * (inpB.y - inpA.y);
}
void get_line(point inpA, point inpB, double &a1, double &b1, double &c1)
{
a1 = inpB.y - inpA.y;
b1 = inpA.x - inpB.x;
c1 = inpA.y * (inpB.x - inpA.x) - inpA.x * (inpB.y - inpA.y);
}
cp cut(point inpA, point inpB, cp incp)
{
cp ret;
point cross;
int i, j;
double t1, t2;
double a1, b1, c1, a2, b2, c2;
ret.n = 0;
for (i = 0; i < incp.n; i++)
{
j = i + 1;
t1 = Cross(inpA, inpB, incp.p[i]);
t2 = Cross(inpA, inpB, incp.p[j]);
if (t1 < eps && t2 < eps)
{
ret.p[ret.n++] = incp.p[i];
ret.p[ret.n++] = incp.p[j];
}
else if (t1 > eps && t2 > eps)
continue;
else
{
get_line(inpA, inpB, a1, b1, c1);
get_line(incp.p[i], incp.p[j], a2, b2, c2);
cross = intersectL(a1, b1, c1, a2, b2, c2);
if (t1 < eps)
{
ret.p[ret.n++] = incp.p[i];
ret.p[ret.n++] = cross;
}
else
{
ret.p[ret.n++] = cross;
ret.p[ret.n++] = incp.p[j];
}
}
}
if (ret.n == 0)
return ret;
for (i = 1, j = 1; i < ret.n; i++)
if (!isEqual(ret.p[i - 1], ret.p[i]))
ret.p[j++] = ret.p[i];
ret.n = j;
if (ret.n != 1 && isEqual(ret.p[ret.n - 1], ret.p[0]))
ret.n--;
ret.p[ret.n] = ret.p[0];
return ret;
}
int main()
{
int n, r;
cp input, ret;
scanf("%d%d", &n, &r);
input.n = n;
for (int i = 0; i < n; i++)
scanf("%lf%lf", &input.p[i].x, &input.p[i].y);
input.p[n] = input.p[0];
ret = input;
for (int i = 0; i < n; i++)
{
point ta, tb, tt;
tt.x = input.p[i + 1].y - input.p[i].y;
tt.y = input.p[i].x - input.p[i + 1].x;
double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);
tt.x = tt.x * k;
tt.y = tt.y * k;
ta.x = input.p[i].x + tt.x;
ta.y = input.p[i].y + tt.y;
tb.x = input.p[i + 1].x + tt.x;
tb.y = input.p[i + 1].y + tt.y;
ret = cut(ta, tb, ret);
}
double ans = -1;
double ans_x1, ans_y1, ans_x2, ans_y2;
for (int i = 0; i < ret.n; i++)
for (int j = 0; j < ret.n; j++)
{
double t = dist(ret.p[i], ret.p[j]);
if (t > ans)
{
ans = t;
ans_x1 = ret.p[i].x;
ans_y1 = ret.p[i].y;
ans_x2 = ret.p[j].x;
ans_y2 = ret.p[j].y;
}
}
printf("%.4lf %.4lf %.4lf %.4lf\n", ans_x1, ans_y1, ans_x2, ans_y2);
return 0;
}
[转载][图论] 给出一个没有偶圈的简单无向图，求两个顶点间路径的数目
发表评论4次阅读2007.09.19 10:08 作者：Felicia 编辑
[阅读更多]
给出一个没有偶圈的简单无向图，求两个顶点间路径的数目。习题：WOJ 1156
老实说，这个题目其实不容易，在正式竞赛中肯定不属于送分题。题目的难点在于发现”没有偶圈”这个条件反映的图的特殊性质。
如提示中所说，考虑图的双连通分量。首先解释一下什么是双连通分量。无向图中某个顶点如果被删除之后，连通分量的数目增加，那么这个顶点就叫做割点。无向图中不包含割点的极大子图就是双连通分量。
双连通分量中任意两顶点共圈。从这个性质出发，可以证明：没有偶圈的简单无向图的所有双连通分量只能是2阶完全图或奇圈，收缩所有双连通分量之后得到的图是树。这两个性质意味着，图中两个顶点间的路径经过的双连通分量的序列是相同的。由此得到以下算法：
- 求出图的所有双连通分量；
- 确定从顶点u到顶点v的一条路径；
- 确定路径经过的双连通分量的序列；
- 确定序列中是奇圈的双连通分量的数目，记为k，则路径数为2k。
在分析上述算法的复杂度之间，先补充一下图的另一个性质。因为图中没有偶圈，所以图中不包含同胚于5阶完全图或3,3完全二部图的子图，根据Kuratowski定理，这个图是平面图，由此可得m = O(n)。
现在来分析算法的复杂度。第1步可以利用J. Hopcroft提出的线性时间算法在O(n + m) = O(n)时间内完成。第2步可以用宽度优先搜索在O(n)时间内实现。第3步可以直接在O(n)时间内实现。第4步是整个算法的瓶颈。 它需要计算一个O(2n/2)的数值。使用一般的算法实现时间复杂度将为O(n2)，如果使用快速正交变换实现时间复杂度将为O(nlogn)。综合以上四个结果，算法的时间复杂度是O(nlogn)。算法的空间复杂度为O(n)。
