关于使用边集数组遍历计算入度的问题
查看原帖
关于使用边集数组遍历计算入度的问题
768692
InoriILU楼主2023/10/17 08:43

如题,使用边集数组遍历计算入度会被 #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;
}

2023/10/17 08:43
加载中...