NOI2008 party

Posted on 2011-07-14 12:23 Mato_No1 阅读(295) 评论(0)  编辑 收藏 引用 所属分类: 图算法NOI
原题见这里(BZOJ和BSOJ都挂了,真杯具,只能借助RQ了囧……)

难度不是很大,就是特殊情况比较多,比较猥琐(不过本题数据弱,就算不考虑所有的特殊情况也能过7个点)。
首先O(NM)的朴素算法很好想到:枚举K,然后给每个结点编号即可。在编号时,先随便指定一个未编号的点,设它的编号为0,然后遍历所有和它相关联的边(这里可以把原图想象成一个无向图),将这些边的另一个端点编上号即可,中间若某个点的编号出现矛盾,则这个K不合法,否则这个K合法。
然后进行优化:合法的K实际上是有限制的,它必然是某个数的因数,具体来说,对这个图进行DFS,并考察其中所有的跨越边和逆向边,对于跨越边<i, j>,设遍历树中i、j间距离为D,则合法的K必然是(D-1)的因数(因为i和遍历树中j的父结点都有指向j的边,它们的编号应相同,而它们之间的距离为(D-1));对于逆向边<i, j>,设遍历树中i、j间距离为D',则合法的K必然是(D'+1)的因数(因为这里形成了一个环,环的长度为(D'+1))。这样一来就明显缩小了K的取值范围,再进行枚举,就可以显著缩短时间。

下面是一些极其猥琐的特殊情况:
(1)根据题意,必须是K类每类都有,因此在尝试编号成功(没有发生任何矛盾)后,还要看一下实际出现的编号数目是否等于K,若小于K,同样不合法;
(2)该图的基图可能不连通,此时对于其基图的每个连通块,其编号互不影响,所以要对每个连通块分别统计实际出现的编号数目,设它们的和为SUM,则不大于SUM的K值均合法(只要中间不出现矛盾),因此可以直接得到最大值为SUM,提前结束;不过,这种特判只有在总共实际出现的编号数目小于K的情况下才能进行;
(3)由于考察的是实际出现的编号数目,因此最后求出的最大值、最小值可能小于3,这时应作出如下处理:若最大值小于3,则无解;若最小值小于3,则将最小值改为3。

本题比较猥琐的数据是第4、5、6个点,分别出现了上述的第(1)、(2)、(3)种特殊情况,此外,这三个点建出的图中竟然没有一条跨越边或逆向边!

代码:
#include <iostream>
#include 
<stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 100000, MAXM = 1100001;
struct edge {
    
int a, b, s, pre, next;
} E0[MAXM], E[MAXM 
+ MAXM];
int n, m0, m, P, len, X[MAXN], No[MAXN], stk[MAXN], st[MAXN], dep[MAXN], V[MAXN], fo[MAXN], Q[MAXN], res0, res1;
bool vst[MAXN], T0[MAXN];
long long T[MAXN], _Z = 0;
void init_d()
{
    re(i, n) E[i].a 
= E[i].pre = E[i].next = E0[i].a = E0[i].pre = E0[i].next = i;
    m0 
= n; if (n % 2) m = n + 1else m = n;
}
void add_edge(int a, int b)
{
    E0[m0].a 
= a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E[m].a 
= a; E[m].b = b; E[m].s = 1; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
    E[m].a 
= b; E[m].b = a; E[m].s = -1; E[m].pre = E[b].pre; E[m].next = b; E[b].pre = m; E[E[m].pre].next = m++;
}
void init()
{
    freopen(
"party.in""r", stdin);
    
int _m, a, b; scanf("%d%d"&n, &_m); init_d();
    re(i, _m) {
        scanf(
"%d%d"&a, &b);
        add_edge(
--a, --b);
    }
    fclose(stdin);
}
int gcd(int a, int b)
{
    
int r;
    
while (b) {
        r 
= a % b; a = b; b = r;
    }
    
return a;
}
void prepare()
{
    
int tp, x, y, ord = 0;
    
bool fd;
    re(i, n) V[i] 
= 0; P = 0;
    re(i, n) 
if (!V[i]) {
        stk[tp 
= 0= i; fo[i] = ord++; V[i] = 1; st[i] = E0[i].next; dep[i] = 0;
        
while (tp >= 0) {
            x 
= stk[tp]; fd = 0;
            
for (int p=st[x]; p != x; p=E0[p].next) {
                y 
= E0[p].b;
                
if (!V[y]) {
                    stk[
++tp] = y; fo[y] = ord++; V[y] = 1; st[y] = E0[y].next; dep[y] = dep[x] + 1; st[x] = E0[p].next; fd = 1break;
                } 
else if (V[y] == 1) P = gcd(P, dep[x] - dep[y] + 1); else if (fo[y] > fo[x]) P = gcd(P, dep[y] - dep[x] - 1);
            }
            
if (!fd) {V[x] = 2; tp--;}
        }
    }
    len 
= 0; re3(i, 3, n) if (!(P % i)) X[len++= i;
}
int test(int K)
{
    re(i, n) {vst[i] 
= 0; No[i] = -1;}
    re(i, K) T0[i] 
= 0;
    
int x, y, No0, sum = 0, sum0 = 0;
    re(i, n) 
if (!vst[i]) {
        No[i] 
= 0; Q[0= i; vst[i] = 1; _Z++if (T[0!= _Z) {T[0= _Z; sum++;} if (!T0[0]) {T0[0= 1; sum0++;}
        
for (int front=0, rear=0; front<=rear; front++) {
            x 
= Q[front];
            
for (int p=E[x].next; p != x; p=E[p].next) {
                y 
= E[p].b; No0 = No[x] + E[p].s;
                
if (No0 == K) No0 = 0else if (No0 == -1) No0 = K - 1;
                
if (No[y] >= 0 && No0 != No[y]) return -1else {
                    No[y] 
= No0;
                    
if (T[No0] != _Z) {T[No0] = _Z; sum++;}
                    
if (!T0[No0]) {T0[No0] = 1; sum0++;}
                }
                
if (!vst[y]) {vst[y] = 1; Q[++rear] = y;}
            }
        }
    }
    
if (sum0 < K) res0 = sum;
    
return sum0;
}
void solve()
{
    
int K, K0; res0 = res1 = -1;
    re(i, len) {
        K 
= X[i]; K0 = test(K);
        
if (K0 != -1) {
            
if (res1 == -1) res1 = K0;
            
if (K0 < K) breakelse res0 = K;
        }
    }
    
if (res0 < 3) res0 = res1 = -1else if (res1 < 3) res1 = 3;
}
void pri()
{
    freopen(
"party.out""w", stdout);
    printf(
"%d %d\n", res0, res1);
    fclose(stdout);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理