P4306的Hack数据TLE了,100分但没通过,求调代码,拜谢大佬!!!
code:
#include <bits/stdc++.h>
using namespace std;
struct node
{
int f,t;
}e[4000005];
int n,m,tot,cnt,num,sum,hd[2005],nt[4000005],l[2005],dfn[2005],w[2005];
int d[2005],x[4000005],y[4000005],b[2005],st[2005],c,a[2005],ans;
void add(int a,int b)
{
e[++tot] = (node){a,b};
nt[tot] = hd[a];
hd[a] = tot;
}
void tarjan(int b)
{
l[b] = ++cnt;
dfn[b] = cnt;
st[++c] = b;
d[b] = 1;
for(int i = hd[b];i != 0;i = nt[i])
{
int u = e[i].t;
if(dfn[u] == 0)
{
tarjan(u);
l[b] = min(l[b],l[u]);
}
else if(d[u] != 0)
{
l[b] = min(l[b],dfn[u]);
}
}
if(l[b] == dfn[b])
{
num++;
while(b != st[c + 1])
{
d[st[c]] = 0;
a[st[c]] = num;
c--;
}
}
}
void fun()
{
for(int i = 1;i <= tot;i++)
{
e[i].f = 0;
e[i].f = 0;
}
tot = 0;
memset(hd,0,sizeof(hd));
memset(nt,0,sizeof(nt));
memset(d,0,sizeof(d));
for(int i = 1;i <= m;i++)
{
if(a[x[i]] != a[y[i]])
{
add(a[x[i]],a[y[i]]);
}
}
}
void dfs(int x)
{
sum += b[x];
for(int i = hd[x];i != 0;i = nt[i])
{
int u = e[i].t;
if(d[u] == 0)
{
d[u] = 1;
dfs(u);
}
}
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
char s[2005];
getchar();
scanf("%s",s);
for(int j = 0;j <= n - 1;j++)
{
if(s[j] == '1')
{
x[++m] = i;
y[m] = j + 1;
add(i,j + 1);
}
}
}
for(int i = 1;i <= n;i++)
{
if(dfn[i] == 0)
{
tarjan(i);
}
}
fun();
for(int i = 1;i <= n;i++)
{
b[a[i]]++;
}
for(int i = 1;i <= num;i++)
{
for(int j = 1;j <= num;j++)
{
d[j] = 0;
}
sum = 0;
d[i] = 1;
dfs(i);
ans += b[i] * (sum - b[i]);
ans += b[i] * b[i];
}
printf("%d",ans);
return 0;
}
求问一下原因,最好说一下怎么改,谢谢!(>^ω^<)