#6WA了,不知道为啥,求大佬
  • 板块P1262 间谍网络
  • 楼主sccogg
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/12 20:49
  • 上次更新2024/7/12 22:17:23
查看原帖
#6WA了,不知道为啥,求大佬
909068
sccogg楼主2024/7/12 20:49
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 3e3 + 7, maxm = 8e3 + 7;
int n, r, edgenum, total, cnt, top;
int head[maxn], money[maxn], dfn[maxn], low[maxn], stack[maxn], belong[maxn], bsum[maxn];
bool instack[maxn], canbuy[maxn];
vector<int> newMap[maxn]; // 邻接表
vector<int> newMap2[maxn]; // 逆向建立的邻接表
vector<int> newToOrigin[maxn];
struct Edge {
	int to, next;
	Edge(int a = 0, int b = 0) :to(a), next(b) {}
}edges[maxm];

void init() {
	for (int i = 1; i <= n; i++) {
		head[i] = money[i] = -1;
		bsum[i] = 2e4 + 7;
	}
}
void add(int u, int v) {
	edges[edgenum] = Edge(v, head[u]);
	head[u] = edgenum++;
}
void Tarjan(int u) {
	dfn[u] = low[u] = ++total;
	instack[u] = true;
	stack[++top] = u;
	for (int i = head[u]; ~i; i = edges[i].next) {
		int v = edges[i].to;
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (instack[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		cnt++;
		int v;
		do {
			v = stack[top--];
			instack[v] = false;
			belong[v] = cnt;
			newToOrigin[cnt].push_back(v);
			if (~money[v])
				bsum[cnt] = min(bsum[cnt], money[v]);
		} while (u != v);
	}
}
void dfs(int u) {
	canbuy[u] = true;
	for (int i = 0; i < newMap[u].size(); i++) {
		int v = newMap[u][i];
		if (!canbuy[v])
			dfs(v);
	}
}

int main() {
	scanf("%d", &n);
	init();
	int p;
	scanf("%d", &p);
	for (int i = 1, u, v; i <= p; i++) {
		scanf("%d%d", &u, &v);
		money[u] = v;
	}
	scanf("%d", &r);
	for (int i = 1, u, v; i <= r; i++) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			Tarjan(i);
	// 上面就是Trajan算法模板
	// 建立新图
	for (int u = 1; u <= n; u++) {
		int bu = belong[u];
		for (int i = head[u]; ~i; i = edges[i].next) {
			int bv = belong[edges[i].to];
			if (bu == bv) continue;
			newMap[bu].push_back(bv);
			newMap2[bv].push_back(bu); // 保存各点的入度
		}
	}
	int ansMoney = 0;
	for (int i = 1; i <= cnt; i++) {
		if (newMap2[i].size() == 0 && bsum[i] <= 2e4) { // 对所有可收买并且入度为0的点进行dfs
			dfs(i);
			ansMoney += bsum[i]; // 计算总价钱
		}
	}
	int ansId = maxn;
	for (int i = 1; i <= cnt; i++) // 遍历所有点,找到不可收买的点中编号最小的点
		if (!canbuy[i]) {
			for (int u = 0; u < newToOrigin[i].size(); u++)
				ansId = min(ansId, newToOrigin[i][u]); // 通过newToOrigin找到一个强连通分量对应的原图中的点
		}
	if (ansId != maxn) // 如果ansId不是初始值,说明有不可收买的点
		printf("NO\n%d", ansId);
	else {
		printf("YES\n%d", ansMoney);
	}
}
2024/7/12 20:49
加载中...