Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「ZJOI2007」最大半连通子图 - 强连通分量

一个有向图 G=(V,E) G = (V, E) 称为半连通的(Semi-Connected),如果满足:

u,vV \forall u, v \in V ,满足 uv u \rightarrow v vu v \rightarrow u ,即对于图中任意两点 u u v v ,存在一条 u u v v 的有向路径或者从 v v u u 的有向路径。

G=(V,E) G' = (V', E') 满足 VV V' \subseteq V E E' E E 中所有跟 V V' 有关的边,则称 G G' G G 的一个导出子图。
G G' G G 的导出子图,且 G G' 半连通,则称 G G' G G 的半连通子图。
G G' G G 所有半连通子图中包含节点数最多的,则称 G G' G G 的最大半连通子图。

给定一个有向图 G G ,请求出 G G 的最大半连通子图拥有的节点数 K K ,以及不同的最大半连通子图的数目 C C 。由于 C C 可能比较大,仅要求输出 C C X X 的余数。

链接

BZOJ 1093

题解

显然,一个强连通分量中的点是半连通的,一条链上的所有点是半连通的。

将原图的强连通分量缩为点,问题转化为求 DAG 上最长路,拓扑排序后 DP 即可。

对于方案统计,求出从起点到每一个点的最长路 d(i) d(i) 后,对于每条边 uv u \rightarrow v ,如果 d(v)=d(u)+s(v) d(v) = d(u) + s(v) s(i) s(i) 表示点 i i 所对应原图的强连通分量大小),则这条边在一条或多条最长路中,对所有在最长路上的边构成的图求路径数即可。

注意重边需要特判。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <tr1/unordered_set>

const int MAXN = 100000;
const int MAXM = 1000000;
const int MAXX = 100000000;

struct Node {
    struct Edge *e, *c;
    struct SCC *s;
    Node *p;
    bool inStack, pushed, visited;
    int dfn, low, d, sum;
} N[MAXN];

struct Edge {
    Node *s, *t;
    Edge *next;

    Edge(Node *s, Node *t) : s(s), t(t), next(s->e) {}
};

struct SCC {
    Node v;
    int size, inDegree, in, len, sum;
} S[MAXN];

inline void addEdge(const int s, const int t) {
    N[s].e = new Edge(&N[s], &N[t]);
}

int n, x;

inline int tarjan() {
    int cnt = 0, ts = 0;
    for (int i = 0; i < n; i++) {
        if (N[i].visited) continue;

        std::stack<Node *> s, t;
        s.push(&N[i]);
        N[i].pushed = true;

        while (!s.empty()) {
            Node *v = s.top();
            if (!v->visited) {
                v->visited = true;
                v->c = v->e;
                t.push(v);
                v->inStack = true;
                v->dfn = v->low = ++ts;
            }

            if (v->c) {
                Edge *&e = v->c;
                if (e->t->inStack) v->low = std::min(v->low, e->t->dfn);
                else if (!e->t->pushed) e->t->pushed = true, e->t->p = v, s.push(e->t);
                e = e->next;
            } else {
                s.pop();

                if (v->dfn == v->low) {
                    SCC *scc = &S[cnt++];
                    scc->v.s = scc;
                    Node *u;
                    do {
                        u = t.top();
                        t.pop();
                        u->inStack = false;
                        u->s = scc;
                        scc->size++;
                    } while (u != v);
                }

                if (v->p) v->p->low = std::min(v->p->low, v->low);
            }
        }
    }

    return cnt;
}

inline void contract() {
    std::tr1::unordered_set<unsigned long long> s;
    for (int i = 0; i < n; i++) {
        for (Edge *e = N[i].e; e; e = e->next) {
            unsigned long long x = (static_cast<unsigned long long>(e->s->s - S) << 32) | static_cast<unsigned long long>(e->t->s - S);
            if (e->s->s != e->t->s && !s.count(x)) {
                s.insert(x);
                // printf("[%ld, %ld]\n", e->s->s - S + 1, e->t->s - S + 1);
                e->s->s->v.e = new Edge(&e->s->s->v, &e->t->s->v);
                e->t->s->inDegree++;
            }
        }
    }
}

inline int dp(const int cnt) {
    std::queue<Node *> q;
    for (int i = 0; i < cnt; i++) {
        // printf("size[%d] = %d\n", i, S[i].size);
        if (S[i].inDegree == 0) q.push(&S[i].v);
        S[i].v.d = S[i].size;
        S[i].in = S[i].inDegree;
    }

    while (!q.empty()) {
        Node *v = q.front();
        q.pop();

        for (Edge *e = v->e; e; e = e->next) {
            e->t->d = std::max(e->t->d, v->d + e->t->s->size);
            if (!--e->t->s->in) {
                q.push(e->t);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < cnt; i++) if (!S[i].v.e) ans = std::max(ans, S[i].v.d);
    return ans;
}

inline int dpSum(const int cnt, const int d) {
    std::queue<Node *> q;
    for (int i = 0; i < cnt; i++) {
        if (S[i].inDegree == 0) {
            q.push(&S[i].v);
            S[i].v.sum = 1;
        }
        S[i].in = S[i].inDegree;
    }

    while (!q.empty()) {
        Node *v = q.front();
        q.pop();

        for (Edge *e = v->e; e; e = e->next) {
            if (e->t->d == v->d + e->t->s->size) (e->t->sum += v->sum) %= x;
            if (!--e->t->s->in) {
                q.push(e->t);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < cnt; i++) if (S[i].v.d == d) (ans += S[i].v.sum) %= x;
    return ans;
}

int main() {
    int m;
    scanf("%d %d %d", &n, &m, &x);

    while (m--) {
        int u, v;
        scanf("%d %d", &u, &v), u--, v--;
        addEdge(u, v);
    }

    int cnt = tarjan();
    contract();

    int d = dp(cnt);

    printf("%d\n", d);
    printf("%d\n", dpSum(cnt, d));

    return 0;
}
最近的文章

「SDOI2013」森林 - LCA + 主席树 + 启发式合并

森林中有 n n 个点,m m 条边,每个点有点权,执行 T T 次操作:

  1. 查询两点间点权的第 k k 小;
  2. 连接两个点,保证图在操作后仍然为森林。

于  BZOJ, SDOI, 主席树, 启发式合并, 并查集, 最近公共祖先 继续阅读
更早的文章

「BZOJ 3280」小 R 的烦恼 - 费用流

程设老师最近要进行一项邪恶的实验,这个实验一共持续 n n 天,第 i i 天需要 ai a_i 个研究生来给他搬砖。研究生毕竟也是人,所以雇佣研究生是需要钱的,机智的程设老师已经联系好了 m m 所大学,第 j j 所大学共有 lj l_j 个研究生,同时雇佣这所大学的一个研究生需要 pj p_j 元钱。

一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生,毫无疑问,就不能再进行工作了。但是机智的老师早早联系好了 k k 家医院,第 i i 家医院医治一个濒死的研究生需要 di d_i 天,并且需要 qi q_i 元钱。

于  BZOJ, Edmonds-Karp, 网络流, 费用流 继续阅读
comments powered by Disqus