逆天输入问题
查看原帖
逆天输入问题
759710
LuoFeng_Nanami楼主2024/3/24 20:57

如题,这份代码在 p,m,np,m,n 输入都正常的情况下,测试点 22 输入到第 30073007 组边就结束了,即原数据第 59105910 行,更离谱的是,理论上应该输出

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;
}
2024/3/24 20:57
加载中...