0 分求调
查看原帖
0 分求调
524911
PassName楼主2024/9/18 20:43

RT,已经改的和第一篇题解一样了仍然输出 0

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e3 + 5;
const int M = 2e5 + 5;

int s, n, m;
int h[N], e[M], ne[M], idx;
struct node
{
	int p[N][5];
	int out[N];
} a[N];
int dfn[N], low[N], siz[N], ins[N], stk[N], c[N];
int num, cnt, top;
int vis[N][N];
int u[N], v[N], ans[N];

void add(int a, int b)
{
    e[++idx] = b, ne[idx] = h[a], h[a] = idx;	
} 

bool flag;
void find(int x, int y, int nx, int ny)
{
	if (a[x].out[nx] == 1 && a[y].out[ny] == 0) 
	{
		flag = 1;
		return ;
	}
	if (vis[nx][ny]) return ;
	vis[nx][ny] = 1;
	find(x, y, a[x].p[nx][0], a[y].p[ny][0]);
	find(x, y, a[x].p[nx][1], a[y].p[ny][1]);
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	stk[++top] = x, ins[x] = 1;
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (ins[y]) low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x])
	{
		cnt++; int y;
		do
		{
			y = stk[top--], ins[y] = 0;
			c[y] = cnt;
		} while (x != y);
	}
}

int get(int x)
{
	if (ans[x]) return ans[x];
	ans[x] = siz[x];
	for (int i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		ans[x] = max(ans[x], get(y) + siz[x]);
	}
	return ans[x];
}

signed main()
{
	cin >> s;
	for (rint i = 1; i <= s; i++)
	{
		cin >> n >> m;
		for (rint j = 1; j <= m; j++)
		{
			int t;
			cin >> t;
			t++;
			a[i].out[t] = 1;
		}
		for (rint l = 1; l <= n; l++)
		{
			int aa, bb;
			cin >> aa >> bb;
			aa++, bb++;
			a[i].p[l][0] = aa;
			a[i].p[l][1] = bb;
		}
	}
	for (rint i = 1; i <= s; i++)
	{
		for (rint j = 1; j <= s; j++)
		{
			if (i == j) continue;
			flag = 0;
			memset(vis, 0, sizeof vis);
			find(i, j, 1, 1);
			if (!flag) 
			{
				add(i, j);
				u[idx] = i;
				v[idx] = j;
			}
		}	
	}
	for (rint i = 1; i <= s; i++) 
	    if (!dfn[i]) 
		    tarjan(i);
	int idxx = idx;
	idx = 0;
	memset(h, 0, sizeof h);
	memset(e, 0, sizeof e);
	memset(ne, 0, sizeof ne);
	for (rint x = 1; x <= idxx; x++)
	{
		for (rint j = h[x]; j; j = ne[j])
		{
			int y = e[j];
			if (c[x] == c[y]) continue;
			add(c[x], c[y]);
		}
	}
	int res = 0;
	for (rint i = 1; i <= cnt; i++)
	    if (!ans[i]) 
		    res = max (res, get(i));
	cout << res << endl;
	return 0;
}
2024/9/18 20:43
加载中...