BZOj4423: [AMPPZ2013]Bytehattan
对偶图 好题 并查集    2016-12-02 20:02:24    292    0    0

4423: [AMPPZ2013]Bytehattan

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 228  Solved: 144
[Submit][Status][Discuss]

Description

比特哈顿镇有n*n个格点,形成了一个网格图。一开始整张图是完整的。
有k次操作,每次会删掉图中的一条边(u,v),你需要回答在删除这条边之后u和v是否仍然连通。

Input

第一行包含两个正整数n,k(2<=n<=1500,1<=k<=2n(n-1)),表示网格图的大小以及操作的个数。
接下来k行,每行包含两条信息,每条信息包含两个正整数a,b(1<=a,b<=n)以及一个字符c(c=N或者E)。
如果c=N,表示删除(a,b)到(a,b+1)这条边;如果c=E,表示删除(a,b)到(a+1,b)这条边。
数据进行了加密,对于每个操作,如果上一个询问回答为TAK或者这是第一个操作,那么只考虑第一条信息,否则只考虑第二条信息。
数据保证每条边最多被删除一次。

Output

输出k行,对于每个询问,如果仍然连通,输出TAK,否则输出NIE。

Sample Input

3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N

Sample Output

TAK
TAK
NIE
NIE

Solution

显然加边比删边容易维护连通性

假如是离线的话,并查集倒着做就可以了

此题强制在线,我们想办法把删边转变成加边

把原图转成对偶图,然后当且仅当两点在同一环上,两点不联通

用并查集维护即可

 

Source code

#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
const int maxn = 1500 + 5;
 
int n;
int m;
char c;
int fa[maxn * maxn];

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

bool flag = 1;

int main() 
{
#define ID(x, y) (x == 0 || y == 0 || x == n || y == n ? n * n + 1 : (x) * n - n + y)

    read(n);
    read(m);

    for (int i = 1; i <= n * n + 1; ++ i) 
        fa[i] = i;

    for (int i = 1, x, y, A, B, u; i <= m; ++ i) {
        if (flag)
            read(x), read(y), scanf("%c", &c), read(u), read(u), getchar();
        else
            read(u), read(u), getchar(), read(x), read(y), scanf("%c", &c);

        if (c == 'N')
            A = find(ID(x, y)), B = find(ID(x - 1, y));
        else
            A = find(ID(x, y)), B = find(ID(x, y - 1));

        A = find(A);
        B = find(B);
        fa[A] = B;

        if (flag = A != B)
            putchar('T'), putchar('A'), putchar('K'), putchar('\n'); 
        else
            putchar('N'), putchar('I'), putchar('E'), putchar('\n'); 
    }
}

 

BZOJ4695: 最假女选手
292 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航