C/C++教程

[USACO15JAN]Grass Cownoisseur G

本文主要是介绍[USACO15JAN]Grass Cownoisseur G，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

link
拿到本题，先强连通缩个点~
得到一个DAG，考虑这个只能逆行一次简直就是分形图的板子嘛。逆行就是第一层向第二层连边即可，这样就保证了只会跑一次。
然后因为这个分形图是个 DAG，所以可以上拓扑排序或者 spfa，，在这里spfa的复杂度=拓扑排序的复杂度。
还有一个值得深思的问题，我们可能从第一层到第二层的时候重复计算了一个点的贡献。最简单的例子：一条边来回走一下，理论上来说会被计算两次没错。
但是，题目要求的是起点为 \(1\)，终点为 \(1\) 的贡献，又因为缩点后这是个 DAG，所以重复的点只会是 \(1\) 所在缩点后的点！多减一次 \(1\) 所在的强连通分量的大小即可。
注意缩点后只有一个点的情况需要特判。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector> 
#include <queue> 
#include <cassert>
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 2e5 + 5;
#define Debug(x) cerr << #x << ' ' << x
#define hh cerr << endl
int n, m, col[MAXN], dfn[MAXN], tot, low[MAXN], s[MAXN], cnt, nk;
int edgex[MAXN], edgey[MAXN], maxx, dp[MAXN], siz[MAXN];
bool vis[MAXN];
vector <int> v[MAXN];
queue <int> que;
// dij 好像不能跑最大值
// 强连通+分层图+spfa（雾 
// 由于原图是个 dag，所以这个分层图也是个 dag，所以可以直接用拓扑排序 
// 其实这个 spfa 的复杂度和 top排序是一样的 / emm
void dfs(int x) {
	dfn[x] = ++ tot; low[x] = tot; s[++ cnt] = x;
	for(uint i = 0; i < v[x].size(); i ++) {
		int y = v[x][i];
		if(!dfn[y]) dfs(y), low[x] = min(low[x], low[y]);
		else if(!col[y]) low[x] = min(low[x], dfn[y]);
	}
	if(dfn[x] == low[x]) {
		nk ++; int t;
		do {
			t = s[cnt --]; col[t] = nk;
		} while(t != x);
	}
}
void spfa() {
	que.push(col[1]); vis[col[1]] = 1; dp[col[1]] = siz[col[1]];
	while(!que.empty()) {
		int t = que.front(); que.pop(); vis[t] = 0;
		for(uint i = 0; i < v[t].size(); i ++) {
			int y = v[t][i];
			if(dp[y] < dp[t] + siz[y]) {
				dp[y] = dp[t] + siz[y]; assert(siz[y] > 0);
				if(!vis[y]) vis[y] = 1, que.push(y);
			}
		}
	}
}
int main() {
	int x, y;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d", &x, &y); v[x].push_back(y); edgex[i] = x; edgey[i] = y;
	}
	for(int i = 1; i <= n; i ++) if(!dfn[i]) dfs(i);
	for(int i = 1; i <= n; i ++) v[i].clear(), siz[col[i]] ++, siz[col[i] + nk] ++;
	for(int i = 1; i <= m; i ++) {
		if(col[edgex[i]] != col[edgey[i]]) {
			v[col[edgex[i]]].push_back(col[edgey[i]]);
			v[col[edgex[i]] + nk].push_back(col[edgey[i]] + nk);
			v[col[edgey[i]]].push_back(col[edgex[i]] + nk);
		}
	}
	spfa(); maxx = max(dp[col[1]], dp[col[1] + nk]);
	if(nk == 1) maxx += siz[col[1]]; // 特判 
	printf("%d", maxx - siz[col[1]]);
	return 0;
}
这篇关于[USACO15JAN]Grass Cownoisseur G的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航