这个题和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关,急!!!拜谢大佬