此题数据过水,求hack
查看原帖
此题数据过水,求hack
775893
OIDragon楼主2024/3/4 21:13

我的AC代码:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    long long u,v;
}a[20005];
long long dfn[20005],w[20005],in[20005],sum,cnt,c[20005],e[20005],mx[20005],d[20005],f[20005];
vector<int> vx[20005],ex[20005];
stack<int> s;
void tarjan(long long u)
{
    s.push(u);
    f[u] = 1;
    dfn[u] = ++cnt;
	w[u] = cnt;
	for(long long i = 0;i < vx[u].size();i++)
	{
        long long nt = vx[u][i];
        if(dfn[nt] == 0)
		{
            tarjan(nt);
            w[u] = min(w[u],w[nt]);
        }
		else if(f[nt] != 0)
		{
        	w[u] = min(w[u],dfn[nt]);
		}
    }
    if(dfn[u] == w[u])
	{
        sum++;
		f[u] = 0;
        c[u] = sum;
        e[sum] = mx[u];
        d[sum] = u;
		while(s.top() != u)
		{
			long long cur = s.top();
			s.pop();
            f[cur] = 0;
            c[cur] = sum;
            e[sum] = min(e[sum],mx[cur]);
			d[sum] = min(d[sum],cur);
		}
    	s.pop();
	}
    return;
}
void mark(long long cur)
{
	if(cur == 0)
	{
		return;
	}
	f[cur] = 1;
	for(long long nxt : ex[cur])
	{
		mark(nxt);
	}
	return;
}
int main()
{
	long long n,p,m,z = 0,ans = 0;
	memset(mx,0x3f,sizeof(mx));
    scanf("%lld%lld",&n,&p);
    for(long long i = 1;i <= p;i++)
	{
		long long x,y;
		scanf("%lld%lld",&y,&x);
		mx[y] = x;
	}
	scanf("%lld",&m);
	for(long long i = 1;i <= m;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		a[i] = {x,y};
		vx[x].push_back(y);
	}
	cnt = 0;
    for(long long i = 1;i <= n;i++)
	{
		if(dfn[i] == 0)
		{
			tarjan(i);
		}
	}
	for(long long i = 1;i <= m;i++)
	{
        long long p = c[a[i].u],q = c[a[i].v];
		if(p != q)
		{
			in[q]++;
			ex[p].push_back(q);
		}
	}
    for(long long i = 1;i <= sum;i++)
	{
		if(in[i] == 0)
		{
			if(e[i] == 0x3f3f3f3f3f3f3f3f)
			{
				z = n + 1;
			}
			else
			{
				ans = ans + e[i];
				mark(i);
			}
		}
	}
	if(z == 0)
	{
		printf("YES\n%lld",ans);
		return 0;
	}
	printf("NO\n");
	for(long long i = 1;i <= n;i++)
	{
		if(mx[i] == 0x3f3f3f3f3f3f3f3f)
		{
			z = min(z,d[c[i]]);
		}
	}
	printf("%lld\n",z);
    return 0;
}

在样例二中输出的是22,但提交却能AC,数据太水!

2024/3/4 21:13
加载中...