2208: [Jsoi2010]连通数

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2208

Description

BZOJ 2208: [Jsoi2010]连通数 tarjan bitset-LMLPHP

Input

输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。

Output

输出一行一个整数,表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

9

HINT

对于100%的数据,N不超过2000。

题意

题解

先缩点,变成一个有向无环图之后,再直接跑dp就好了

可以用bitset做

代码:

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200051
#define mod 10007
#define eps 1e-9
int Num;
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** vector<int> Q[maxn];
char s[];
int dfn[],low[],_clock=;
int sta[],top;
bool in_sta[];
int changed[],scc,num[];
bitset<> have[];
void tarjan(int x)
{
dfn[x]=low[x]=++_clock;
sta[++top]=x;
in_sta[x]=;
for(int i=;i<Q[x].size();i++)
{
int v = Q[x][i];
if(!dfn[v])
tarjan(v),low[x]=min(low[x],low[v]);
else if(in_sta[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
int temp;
++scc;
do{
temp = sta[top--];
in_sta[temp]=;
changed[temp]=scc;
++num[scc];
}while(temp!=x);
}
}
int main()
{
int n=read();
for(int i=;i<=n;i++)
{
scanf("%s",s+);
for(int j=;j<=n;j++)
{
if(s[j]=='')
Q[i].push_back(j);
}
}
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=;i<=n;i++)
have[changed[i]][i]=;
int ans=;
for(int i=;i<=scc;i++)
{
ans+=num[i]*num[i];
bitset<>temp;
for(int x = ;x<=n;x++)
{
if(changed[x]==i)
{
for(int j=;j<Q[x].size();j++)
{
int v = Q[x][j];
if(changed[v]!=i)
temp|=have[changed[v]];
}
}
}
ans+=num[i]*temp.count();
have[i]|=temp; }
printf("%d\n",ans);
}
05-04 08:42