rt,#6 输入感觉有点奇怪:
2
1
2 512
2
1 2
2 1
最后一行是一个奇怪的字符(clion里打开显示 SUB,现在在洛谷上编辑区是个红点,预览里是空的)
输出:
YES
512
本地测试通过,不知道为什么洛谷上 RE。
代码:
// P1262 间谍网络
#include<bits/stdc++.h>
using namespace std;
const int N = 3010, M = 8010;
int n, m, p;
class Graph {
private:
vector<int> G[N];
public:
int inDegree[N];
void addEdge(int u, int v) {
G[u].push_back(v);
inDegree[v]++;
}
vector<int> operator[](int idx) {
return G[idx];
}
};
class Node {
public:
int id;
bool canBuy;
int cost;
};
vector<Node> nodes;
int dfn[N], low[N], color[N], idx = 0, sccCnt = 0;
bool isBuyable[N];
int minCost[N], minId[N];
stack<int> s;
void tarjan(int u, Graph& G) {
dfn[u] = low[u] = ++idx;
s.push(u);
for (auto v : G[u]) {
if (!dfn[v]) {
tarjan(v, G);
low[u] = min(low[u], low[v]);
} else if (!color[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
sccCnt++;
while (!s.empty()) {
int x = s.top();
s.pop();
color[x] = sccCnt;
minId[sccCnt] = min(minId[sccCnt], x);
if (nodes[x].canBuy) {
isBuyable[sccCnt] = 1;
minCost[sccCnt] = min(minCost[sccCnt], nodes[x].cost);
}
if (x == u) break;
}
}
}
int main() {
memset(minCost, 0x3f, sizeof(minCost));
memset(minId, 0x3f, sizeof(minId));
Graph G, reG;
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++) {
nodes.push_back(Node{i, 0, 0});
}
for (int i = 1; i <= p; i++) {
int id, x;
scanf("%d%d", &id, &x);
nodes[id].canBuy = 1, nodes[id].cost = x;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G.addEdge(u, v);
}
for (int i = 1; i <= n; i++) {
if (nodes[i].canBuy && !dfn[i]) tarjan(i, G);
}
bool valid = 1;
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
valid = 0;
printf("NO\n%d\n", i);
break;
}
}
if (!valid) return 0;
printf("YES\n");
for (int i = 1; i <= n; i++) {
for (auto v : G[i]) {
if (color[i] != color[v]) {
reG.addEdge(color[i], color[v]);
}
}
}
long long ans = 0;
for (int i = 1; i <= sccCnt; i++) {
if (reG.inDegree[i]) continue;
ans += minCost[i];
}
printf("%lld\n", ans);
return 0;
}
thx!