如题,这份代码在 p,m,n 输入都正常的情况下,测试点 2 输入到第 3007 组边就结束了,即原数据第 5910 行,更离谱的是,理论上应该输出
NO
1506
但是我这份代码竟输出了
NO
2901
这是怎么回事???
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i, a, b) for(rll i = a; i <= b; i++)
#define Fdn(i, a, b) for(rll i = a; i >= b; i--)
#define int ll
#define pii pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f,mod = 1e9 + 7;
const int maxn = 3e3 + 7, maxm = 8e3 + 7;
int n, m;
int x[maxn], y[maxn];
int val[maxn];
bool tag[maxn];
int dfn[maxn], low[maxn], dfn_clock;
int f[maxn], stk[maxn], top;
int scccnt, col[maxn];
bool ins[maxn], _tag[maxn];
vector<int> G[maxn];
inline void Tarjan(int u) {
cout << u << '\n';
dfn[u] = low[u] = ++dfn_clock, ins[u] = 1, stk[++top] = u;
for(int v : G[u]) {
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if(ins[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
scccnt++;
while(stk[top] != u)
{ col[stk[top]] = scccnt; f[scccnt] = min(f[scccnt], val[stk[top]]); ins[stk[top--]] = 0; }
col[stk[top]] = scccnt; f[scccnt] = min(f[scccnt], val[stk[top]]); ins[stk[top--]] = 0;
}
}
signed main(){
freopen("P1262_2.in", "r", stdin);
freopen("P1262.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(f, 0x3f, sizeof f);
memset(val, 0x7f, sizeof val);
cin >> n;
int p; cin >> p;
//cout << "asjahsjagsjhasha" << p << '\n';
F(i, 1, p) {
int id, v; cin >> id >> v;
tag[id] = 1, val[id] = v;
}
cin >> m;
//cout << " a" << m << '\n';
F(i, 1, m) {
cin >> x[i] >> y[i];
G[x[i]].push_back(y[i]);
//cout << x[i] << ' ' << y[i] << '\n';
//cout << i << '\n';
}
F(i, 1, n) {
if(tag[i] && !dfn[i]) Tarjan(i);
}
F(i, 1, n) {
if(!dfn[i]) { cout << "NO\n" << i; return 0; }
}
cout << "YES\n";
//F(i, 1, n) cout << col[i] << '\n';
F(i, 1, m) {
if(col[x[i]] != col[y[i]])
_tag[col[y[i]]] = 1;
} int ans = 0;
F(i, 1, scccnt)
if(!_tag[i])
ans += f[i];
cout << ans << '\n';
return 0;
}