玄5关急求解,大佬帮忙!
  • 板块灌水区
  • 楼主Cat_YydS
  • 当前回复16
  • 已保存回复16
  • 发布时间2024/3/14 21:59
  • 上次更新2024/3/15 12:26:02
查看原帖
玄5关急求解,大佬帮忙!
922482
Cat_YydS楼主2024/3/14 21:59

P4306的Hack数据TLE了,100分但没通过,求调代码,拜谢大佬!!!

code: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; 
}

求问一下原因,最好说一下怎么改,谢谢!(>^ω^<)

2024/3/14 21:59
加载中...