bzoj 1098 [POI2007] 办公楼 biu

# 解题思路

画画图可以发现，只要是两个点之间没有相互连边，那么就必须将这两个人安排到同一个办公楼内，如图所示：

那，我们可以建立补图，就是先建一张完全图，然后把题目中给出的边都删掉，这就是一张补图，显然补图中相互连边的点就放在同一栋办公楼内。

我们可以用并查集来完成，但是数据范围显然不允许用这样的方法，建图的复杂度是 $N^2$ 的。所以考虑另一种方法：

将原图建立好，在原图中，从一个点开始，把这个点所能够直接到达的点标记出来，这些点是不可以放在一起的。然后将这些点删除。

之后对每一个点都进行这样的操作，那么之后要删除的点都要满足既没有被删除也没有被标记。这样做下来的复杂度还是 $N^2$ 的。再来想想如何优化，我们如果在删点的时候，不去枚举那些已经被删除的点。那所有的删点的操作总时间复杂度是 $M$ 的，因为每个边都要只遍历一次。如何优化？链表啊。。。

# 附上代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

template <typename T> inline void read(T &x) {

    x = ; T f = ; char c = getchar();

    while (c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while (c <= '' && c >= '') {x = x* + c-''; c = getchar();}

    x *= f;

}

const int maxn = 4e6+;

int n, m, head[maxn], cnt, ans, pre[maxn], sur[maxn], num[maxn];

bool vis[maxn], del[maxn];

struct edge {int nxt, to;}ed[maxn];

inline void addedge(int x, int y) {

    ed[++cnt].nxt = head[x], head[x] = cnt, ed[cnt].to = y;

}

inline void DEL(int x) {

    sur[pre[x]] = sur[x];

    pre[sur[x]] = pre[x];

    del[x] = ;

}

inline void BFS(int u) {

    queue<int> Q;

    Q.push(u), vis[u] = ;

    while (!Q.empty()) {

        int now = Q.front();

        Q.pop();

        num[ans] ++;

        for(int i=head[now]; i; i=ed[i].nxt)

            vis[ed[i].to] = ;

        for(int i=sur[]; i<=n; i=sur[i])

            if(!vis[i] && !del[i]) Q.push(i), DEL(i);

        for(int i=head[now]; i; i=ed[i].nxt)

            vis[ed[i].to] = ;

    }

}

int main() {

    read(n), read(m);

    int u, v;

    for(int i=; i<=m; i++) {

        read(u), read(v);

        addedge(u, v), addedge(v, u);

    }

    for(int i=; i<=n; i++)

        pre[i] = i-, sur[i] = i+;

    for(int i=; i<=n; i++)

        if(!del[i]) del[i] = , ans ++, BFS(i), DEL(i);

    sort(num+, num++ans);

    printf("%d\n", ans);

    for(int i=; i<=ans; i++) printf("%d ", num[i]);

    return ;

}

秒客网

bzoj 1098 [POI2007] 办公楼 biu

# 解题思路

# 附上代码

相关文章