两个题目的区别?
  • 板块灌水区
  • 楼主OIDragon
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/10 10:43
  • 上次更新2024/3/10 10:47:07
查看原帖
两个题目的区别?
775893
OIDragon楼主2024/3/10 10:43

这个题和P2194的区别是什么?为什么在P2195AC的代码,提交到这个题就WA#10呢?

附代码,求调:

#include <bits/stdc++.h>
using namespace std;
struct edge 
{
	int v,nt;
}e[300005];
int n,m,hd[100005],tot,b[100005],a[100005];
int w[100005],dfn[100005],c[100005],cnt,mn[100005],z[100005],sum;
stack<int> s;
void add(int u,int v)
{
	tot++;
	e[tot].v = v;
	e[tot].nt = hd[u];
	hd[u] = tot;
}
void tarjan(int u)
{
	dfn[u] = ++sum;
	w[u] = sum;
	a[u] = 1;
	s.push(u);
	for(int i = hd[u];i != 0;i = e[i].nt)
	{
		int v = e[i].v;
		if(dfn[v] == 0)
		{
			tarjan(v);
			w[u] = min(w[u],w[v]);
		}
		else if(a[v] != 0)
		{
			w[u] = min(w[u],dfn[v]);
		}
	}
	if(w[u] == dfn[u])
	{
		int v;
		cnt++;
		do
		{
			v = s.top();
			s.pop();
			a[v] = 0;
			c[v] = cnt;
			if(b[v] < mn[cnt])
			{
				mn[cnt] = b[v];
				z[cnt] = 1;
			}
			else if(b[v] == mn[cnt])
			{
				z[cnt]++;
			}
		}while(v != u);
	}
}
int main()
{
	memset(mn,0x3f,sizeof(mn));
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&b[i]);
	}
	scanf("%d",&m);
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i = 1;i <= n;i++)
	{
		if(dfn[i] == 0)
		{
			tarjan(i);
		}
	}
	int x = 0,ans = 1;
	for(int i = 1;i <= cnt;i++)
	{
		x += mn[i];
		ans *= z[i];
		ans %= 1000000007;
	}
	printf("%d %d",x,ans);
	return 0;
}

玄3关,急!!!拜谢大佬

2024/3/10 10:43
加载中...