从P2194过来的,求查错
查看原帖
从P2194过来的,求查错
200044
JS_TZ_ZHR楼主2020/5/29 21:25

不知道为什么同样的代码P2194AC这个却WA

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m,sum[100005],u,v,dfn[100005],cnt,low[100005],total,color[100005],dis[100005];
int ans1,in[100005];
long long ans2=1,num[100005];
bool vis[100005];
vector<int>ve[100005];
stack<int>s;
void tarjan(int now) {
	dfn[now]=low[now]=++cnt;
	s.push(now);
	vis[now]=true;
	for(int i=0; i<ve[now].size(); i++) {
		if(!dfn[ve[now][i]]) {
			tarjan(ve[now][i]);
			low[now]=min(low[now],low[ve[now][i]]);
		} else if(vis[ve[now][i]])
			low[now]=min(low[now],dfn[ve[now][i]]);
	}
	if(low[now]==dfn[now]) {
		total++;
		while(1) {
			int temp=s.top();
			color[s.top()]=total;
			if(sum[s.top()]==dis[total])num[total]++;
			if(sum[s.top()]<dis[total])dis[total]=sum[s.top()],num[total]=1;
			vis[s.top()]=false;
			s.pop();
			if(now==temp)break;
		}
	}
	return;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&sum[i]),dis[i]=1e9,num[i]=1;
	scanf("%d",&m); 
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&u,&v);
		ve[u].push_back(v);
	}
	for(int i=1; i<=n; i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=0;j<ve[i].size();j++){
			if(color[i]!=color[ve[i][j]])in[color[ve[i][j]]]++;
		}
	}
	for(int i=1;i<=total;i++)ans1+=dis[i],ans2=(ans2*num[i])%mod;
	printf("%d %lld\n",ans1,ans2);
	return 0;
}
2020/5/29 21:25
加载中...