90pts 求助!!!
查看原帖
90pts 求助!!!
1085005
NulliT_Y楼主2024/11/27 16:56

看了题解的用h[i][j]h[i][j]表示强连通分量iijj的写法,但是不知道自己的方法错哪 orz

#include<bits/stdc++.h>

using namespace std;
#define lowbit(x) x & -x
#define int long long
#define pii pair<int ,int >
#define  fi first
#define se second
#define ull unsigned long long

#define find1(x) __builtin_popcount(x)

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;
const long long INF=0x3f3f3f3f3f3f3f3f;

mt19937_64 rnd(random_device{}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX); // use dist(rnd)

int  dfn[N] , scc[N] , low[N], stk[N] , V[N];
int tot = 0 , scc_cnt = 0 , top;

vector<int > edge[N] , E[N];
int In[N];
int dp[N];
void  Tarjan(int u) 
{
	dfn[u] = low[u] = ++tot;
	
	stk[++top] = u;
	for(auto v : edge[u])
	{
		if(!dfn[v])
		{
			
			Tarjan(v);
			low[u] = min(low[u] , low[v]);
		}
		else if(!scc[v])
		{
			low[u] = min(low[u] , dfn[v]);
		}
	}
	if(dfn[u] == low[u])
	{
		int x;
		scc_cnt ++;
		do
		{
			x = stk[top--];
			scc[x] = scc_cnt; 
			V[scc_cnt] ++;
		}while(x != u);
	}
}
int Ans ;

void solve() {
	int n ;
	cin >> n ;
	
	for(int i = 1 ; i <= n; i  ++)
	{
		string s ;
		cin >> s; 
		s = ' ' + s;
		for(int j = 1 ; j <= n ; j ++)
		{
			if(j == i) continue;
			if(s[j] == '1')
			{
				edge[i].push_back(j);
			}
		}
	}
	
	
	
	for(int i = 1 ; i <= n ; i ++)
	{
		if(!dfn[i]) Tarjan(i);
	}

	
	int root = 0 ;
	for(int i = 1 ; i <= n ; i ++)
	{
		for(auto v : edge[i])
		{
			int u = scc[i];
			v = scc[v];
			if(u != v)
			{
				E[v].push_back(u);
				In[u] ++;
			}
		}
	}
	queue<int > q ;
	for(int i  = 1  ; i <= scc_cnt ; i ++)
	{
		if(!In[i]) q.push(i);
		dp[i] = V[i];
	}
	
	while(q.size())
	{
		int u = q.front();
		q.pop();
		Ans += (dp[u]) * V[u];
		// cout << "Ans = " << Ans << '\n';
		for(auto v : E[u])
		{
			In[v] --;
			dp[v] += dp[u];
			if(In[v] == 0)
			{
				q.push(v);
			}
		}
	}
	cout << Ans << '\n';
	
}






#undef int
int main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cout<<fixed<<setprecision(15);
  
  
  
  // int _ = 1;cin >>_;while(_--)
  {
    solve();
  }
  return 0;
}
2024/11/27 16:56
加载中...