1 条题解

  • 1
    @ 2022-8-30 10:03:11
    #include<bits/stdc++.h>
    using namespace std;
    
    #define int long long
    int s, n, m;
    const int maxn = 205;
    int cnt, hd[maxn];
    struct node{
    	int to, nxt;
    }e[305];
    struct node2{
    	int lin[maxn][5], out[maxn];
    }a[maxn];
    int dfn[maxn], low[maxn], siz[maxn], co[maxn], st[maxn];
    int tmp, top, col;
    int flag, vis[maxn][maxn];
    int u[305], v[305], ans[maxn];
    
    void add (int u, int v)
    {
    	e[++cnt].to = v;
    	e[cnt].nxt = hd[u];
    	hd[u] = cnt;
    }
    
    void input ()
    {
    	scanf ("%lld", &s);
    	for (int i = 1; i <= s; i++)
    	{
    		scanf ("%lld %lld", &n, &m);
    		for (int j = 1; j <= m; j++)
    		{
    			int t;
    			scanf ("%lld", &t);
    			t++;
    			a[i].out[t] = 1;
    		}
    		for (int l = 1; l <= n; l++)
    		{
    			int aa, bb;
    			scanf ("%lld %lld", &aa, &bb);
    			aa++, bb++;
    			a[i].lin[l][0] = aa, a[i].lin[l][1] = bb;
    		}
    	}
    }
    
    void find (int x, int y, int nx, int ny)
    {
    	if (a[x].out[nx] == 1 and a[y].out[ny] == 0) 
    	{
    		flag = 1;
    		return;
    	}
    	if (vis[nx][ny]) return;
    	vis[nx][ny] = 1;
    	find (x, y, a[x].lin[nx][0], a[y].lin[ny][0]);
    	find (x, y, a[x].lin[nx][1], a[y].lin[ny][1]);
    }
    
    void build ()
    {
    	for (int i = 1; i <= s; i++)
    	{
    		for (int 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[cnt] = i, v[cnt] = j;
    		}	
    	}
    }
    
    void tarjan (int u)
    {
    	dfn[u] = low[u] = ++tmp;
    	st[++top] = u;
    	for (int i = hd[u]; i; i = e[i].nxt)
    	{
    		int v = e[i].to;
    		if (!dfn[v])
    		{
    			tarjan (v);
    			low[u] = min (low[u], low[v]);
    		}
    		else if (!co[v]) low[u] = min (low[u], dfn[v]);
    	}
    	if (dfn[u] == low[u])
    	{
    		co[u] = ++col;
    		siz[col] = 1;
    		while (st[top] != u)
    		{
    			co[st[top]] = col;
    			siz[col]++;
    			top--;
    		}
    		top--;
    	}
    }
    
    void rebuild ()
    {
    	for (int i = 1; i <= s; i++) if (!dfn[i]) tarjan (i);
    	int recoc = cnt;
    	cnt = 0;
    	memset (hd, 0, sizeof hd);
    	memset (e, 0, sizeof e);
    	for (int i = 1; i <= recoc; i++)
    	{
    		if (co[u[i]] == co[v[i]]) continue;
    		add (co[u[i]], co[v[i]]);
    	}
    }
    
    int get (int u)
    {
    	if (ans[u]) return ans[u];
    	ans[u] = siz[u];
    	for (int i = hd[u]; i; i = e[i].nxt)
    	{
    		int v = e[i].to;
    		ans[u] = max (ans[u], get (v) + siz[u]);
    	}
    	return ans[u];
    }
    
    void output ()
    {
    	int anss = 0;
    	for (int i = 1; i <= col; i++) if (!ans[i]) anss = max (anss, get (i));
    	printf ("%lld\n", anss);
    }
    
    signed main ()
    {
    	input ();
    	build ();
    	rebuild ();
    	output ();
    	return 0;
    }
    
    • 1

    信息

    ID
    1272
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    1
    已通过
    0
    上传者