如题,使用边集数组遍历计算入度会被 #9 号数据即网格图卡为 WA 。 才疏学浅,请问这是为什么 qwq 注释处为标题所问。
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
const int MAXN{ 3000 + 5 };
const int MAXM{ 8000 + 5 };
const long long INF{ LLONG_MAX };
typedef int NodeType;
typedef int EdgeType;
typedef long long DataType;
struct Edge
{
NodeType end;
EdgeType next;
};
Edge G[MAXM]{};
NodeType head[MAXN]{};
EdgeType count{};
DataType value[MAXN]{};
NodeType dfn[MAXN]{}, low[MAXN]{}, dn{};
NodeType stack[MAXN]{}, top{};
NodeType group[MAXN]{};
EdgeType newcnt{};
DataType newval[MAXN]{};
bool visit[MAXN]{}; //标记是否在栈中
NodeType s[MAXM]{}, t[MAXM]{};
NodeType indeg[MAXN]{};
void addedge(NodeType start, NodeType end)
{
G[++count].end = end;
G[count].next = head[start];
head[start] = count;
}
void dfs(NodeType now = 1)
{
using std::min;
visit[now] = true;
stack[++top] = now;
dfn[now] = low[now] = ++dn; // 将 low[now] 初始化为 dn 不会导致错误, 且一般都这么写
for (int i{ head[now] }, end{}; i; i = G[i].next)
{
end = G[i].end;
if (!dfn[end]) //若为树边
{
dfs(end);
low[now] = min(low[now], low[end]); //因为儿子可能非割点,所以 low 可能会小
}
else if (visit[end]) low[now] = min(low[now], dfn[end]); //若不为树边,判断 visit 与否?
}
if (dfn[now] == low[now])
{
newcnt++;
while (now != stack[top + 1])
{
group[stack[top]] = newcnt;
newval[newcnt] = min(newval[newcnt], value[stack[top]]);
visit[stack[top--]] = false;
}
}
}
int main()
{
using namespace std;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
NodeType n{}, p{};
EdgeType m{};
DataType ans{};
fill(value, value + MAXN, INF);
fill(newval, newval + MAXN, INF);
cin >> n >> p;
for (NodeType i{}, opt{}, val{}; i < p; i++)
{
cin >> opt >> val;
value[opt] = val;
}
cin >> m;
for (EdgeType i{}; i < m; i++)
{
cin >> s[i] >> t[i];
addedge(s[i], t[i]);
}
for (NodeType i = 1; i <= n; i++) if (!dfn[i] && value[i] != INF) dfs(i);
for (NodeType i = 1; i <= n; i++)
{
if (!dfn[i])
{
cout << "NO" << endl << i << endl;
return 0;
}
}
//for (NodeType i{}; i < n; i++)
// if (group[s[i]] != group[t[i]])
// indeg[group[t[i]]]++;
for (NodeType i = 1; i <= n; i++)
for (EdgeType j = head[i]; j; j = G[j].next)
if (group[i] != group[G[j].end])
indeg[group[G[j].end]]++;
for (EdgeType i = 1; i <= newcnt; i++)
if (!indeg[i])
ans += newval[i];
cout << "YES" << endl << ans << endl;
}