萌新求助90分
查看原帖
萌新求助90分
481851
Withers楼主2022/7/9 13:55

RT,缩点+拓扑排序,不知道哪里错了

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define Withers using
#define AK namespace
#define IOI std;
#define ACM __gnu_pbds 
Withers AK IOI;
Withers AK ACM;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,u,v,w,x,y,z,t,l,r,minn=INT_MAX,maxx=INT_MIN,len,res,pos,id,as,k;
int a[200010];
string s;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define endl '\n'
#define rd read
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
#define deb(x) cout<<#x<<"="<<x<<" ";
vector<int> g1[200010],g[200010];
int cnt1,cnt2;
bool vis1[100010],vis2[200010];
int st[100010];
int from[100010];
bool vis[100010];
int sum=0;
void dfs(int u)
{
	if(vis1[u]) return;
	vis1[u]=1;
	//cout<<u<<endl;
	for(auto i:g[u])
	{
		if(vis1[i]) continue;
		dfs(i);
	}
	st[++cnt1]=u;
}
void dfs2(int u)
{
	//cout<<u<<"nmsl\n\n";
	if(vis2[u]) return;
	vis2[u]=1;
	sum+=1;
	from[u]=cnt2;
	//cout<<u<<" "<<cnt2<<endl;
	for(auto i:g1[u])
	{
		//cout<<i<<" "<<u<<"qwq\n";
		if(vis2[i]) continue;
		dfs2(i);
		//cout<<i<<" "<<u<<"qwq\n";
	}
}
int siz[100010];//dp[100010];
vector<int> f[100010];
int in[100010];
//bool add[2010][2010];
bitset<2010> dp[2010];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;//rd(m);
	// for(int i=1;i<=n;i++) rd(a[i]);
	// for(int i=1;i<=m;i++)
	// {
		// // rd(u);rd(v);
		// // g[u].push_back(v);
		// // g1[v].push_back(u);
	// }
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		//cout<<s<<endl;
		for(int j=0;j<n;j++)
		{
			if(s[j]=='1') g[i].push_back(j+1),g1[j+1].push_back(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis1[i]) dfs(i);
	}
	for(int i=n;i>=1;i--)
	{
		//cout<<st[i]<<"awa\n";
		if(!vis2[st[i]]) 
		{
			cnt2++;
			sum=0;
			dfs2(st[i]);
			siz[cnt2]=sum;
		}
	}
	//cout<<cnt1<<" "<<cnt2<<'\n';
	for(int i=1;i<=n;i++)
	{
		for(auto j:g[i])
		{
			if(from[i]!=from[j]&&!dp[from[i]][from[j]])
			{
				f[from[i]].push_back(from[j]);
				dp[from[i]][from[j]]=1;
				in[from[j]]++;
				//cout<<from[i]<<" "<<from[j]<<endl;
			}
		}
	}
	ll sum=0;
	for(int i=1;i<=cnt2;i++) dp[i][i]=1;
	memset(vis,0,sizeof(vis));
	queue<int> q;
	for(int i=1;i<=cnt2;i++) if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(auto i:f[u])
		{
			dp[i]|=dp[u];
			if(!(--in[i])) q.push(i);
		}
	}
	for(int i=1;i<=cnt2;i++)
	{
		for(int j=1;j<=cnt2;j++)
		{
			//cout<<add[i][j]<<'\n';
			if(dp[i][j]) sum+=1ll*siz[i]*siz[j];
		}
	}
	cout<<sum;
}
// POWERED BY WITHERS
// THINK ONCE, CODE TWICE
2022/7/9 13:55
加载中...