M_sea

洛谷4306 [JSOI2010]连通数
Luogu分析写错一堆东西,交了一版才过。MMP这题数据比较水,Tarjan缩点+Dfs就能氵过去了。先缩点,然后...
扫描右侧二维码阅读全文
01
2018/11

洛谷4306 [JSOI2010]连通数

Luogu

分析

写错一堆东西,交了一版才过。MMP

这题数据比较水,Tarjan缩点+Dfs就能氵过去了。

先缩点,然后对每个点Dfs,把每个访问到的强联通分量的点数加到答案里去。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

const int MAXN=2000+10;
const int MAXM=MAXN*MAXN;

struct Edge { int v,nxt; };
Edge e[MAXM];
int x[MAXM],y[MAXM];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m;
int dfn[MAXN],low[MAXN];
int belong[MAXN],sum[MAXN];
int sta[MAXN],in[MAXN],top=0;
int tot=0,dfs_clock=0;

inline void Tarjan(int u) {
    low[u]=dfn[u]=++dfs_clock;
    sta[++top]=u; in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot; int now;
        while (1) {
            now=sta[top--];
            belong[now]=tot;
            in[now]=0;
            sum[tot]++;
            if (now==u) break;
        }
    }
}

int vis[MAXN];
int ans=0;

inline void Dfs(int u,int anc) {
    ans+=sum[u],vis[u]=anc;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (vis[v]!=anc) Dfs(v,anc);
    }
}

char tmp[MAXN];

int main() {
    scanf("%d\n",&n);
    for (re int i=1;i<=n;i++) {
        scanf("%s",tmp+1);
        for (re int j=1;j<=n;j++) {
            if (tmp[j]=='1') {
                addEdge(i,j);
                ++m; x[m]=i,y[m]=j;
            }
        }
    }
    for (re int i=1;i<=n;i++)
        if (!dfn[i]) Tarjan(i);
    cnt=0; memset(head,0,sizeof(head));
    for (re int i=1;i<=m;i++) {
        int u=x[i],v=y[i];
        if (belong[u]!=belong[v])
            addEdge(belong[u],belong[v]);
    }
    for (re int i=1;i<=n;i++) Dfs(belong[i],i);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 19 PM

发表评论