【题解】P3119 [USACO15JAN] Grass Cownoisseur

题意

传送门

题意很简单，给定一张有向图，允许选择在一条边上反向行走一次，求从1出发，且最终回到1，最多能遍历到的点数。

Solution

一道综合性的图论好题。

首先想到，对于一个强连通分量内的点，都可以互相到达，直接缩成一个点，使原图变为DAG，并给每个强连通分量赋一个权值，为这个强联通分量内的点数。

然后对于一张DAG，考虑实现反向行走一次的条件。这时我们又发现，反向行走一次后，并不改变图的结构，仅仅改变了自身的状态（可以反向走–>不能反向走）。于是可以用分层图解决。

我们对于一张缩点后的DAG，先复制一层，表示反向走一次后的图。由于图的结构不发生任何改变，所以直接复制原图即可。

接着考虑在两层之间连边。设$1$1 ~ $n$n表示原图的点，$n+1$n+1 ~ $2n$2n表示第二层的点，那么假设原图有一条有向边$(x,y)$(x,y)，我们就连接$(y,x+n)$(y,x+n)这样一条边，也就是从终点反向走到起点，由于使用了唯一一次反向机会，所以连到第二层。

接着来考虑边权的问题，设$val$val表示点的权值，那么我们考虑把点权释放到边权上，这样方便跑$SPFA$SPFA。由于题目要求回到起点1，那么说明这条路径表示在原图上一定是一个环（经过分层后不是环，终点变为了$n+1$n+1），所以一路经过的点虽然比边数量多1，但是起点和终点是重复的，所以我们在建图的时候建形如$(x,y,val[y])$(x,y,val[y])的边即可（边权是这条边终点的点权）。

最后要求的是经过点的数量最多，于是跑一边$SPFA​$SPFA​最长路就没了。

Code

小技巧：把$tarjan$tarjan缩点的部分单独写成一个$namespace$namespace，防止变量名的冲突，使主程序更清晰。但别忘了都加上$::$::。

#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 400005
using namespace std;

int n, m, tot, cnt;
int root[MAXN], sz[MAXN];
int head[MAXN], vet[MAXM], Next[MAXM], cost[MAXM];

namespace tj {
	int cnt = 0, T = 0;
	int head[MAXN], Next[MAXM], vet[MAXM];
	void add(int x, int y) {
		cnt++;
		Next[cnt] = head[x];
		head[x] = cnt;
		vet[cnt] = y;
	}

	int low[MAXN], dfn[MAXN], vis[MAXN];
	stack<int> s;
	void tarjan(int x) {
		low[x] = dfn[x] = ++T;
		vis[x] = true;
		s.push(x);
		for(int i = head[x]; i; i = Next[i]) {
			int v = vet[i];
			if(!dfn[v]) {
				tarjan(v);
				low[x] = min(low[x], low[v]);
			} else if(vis[v]) {
				low[x] = min(low[x], dfn[v]);
			}
		}
		if(low[x] == dfn[x]) {
			tot++;
			int t = -1;
			while(t != x) {
				t = s.top();
				s.pop();
				vis[t] = false;
				root[t] = tot;
				sz[tot]++;
			}
		}
	}
}

void add(int x, int y, int w) {
	cnt++;
	Next[cnt] = head[x];
	head[x] = cnt;
	vet[cnt] = y;
	cost[cnt] = w;
}

void rebuild(){
	for(int i = 1; i <= n; i++){
		for(int j = tj::head[i]; j; j = tj::Next[j]){
			int v = tj::vet[j];
			if(root[i] != root[v]){
				int x = root[i], y = root[v];
				add(x, y, sz[y]);
				add(x+tot, y+tot, sz[y]);
				add(y, x+tot, sz[x]);
			}
		}
	}
}

int dis[MAXN], vis[MAXN];
queue<int> q;
void spfa(int s){
	memset(dis, 128, sizeof(dis));
	q.push(s);
	dis[s] = 0;
	vis[s] = true;
	while(!q.empty()){
		int t = q.front();
		q.pop();
		vis[t] = false;
		for(int i = head[t]; i; i = Next[i]){
			int v = vet[i];
			if(dis[v] < dis[t]+cost[i]){
				dis[v] = dis[t]+cost[i];
				if(!vis[v]){
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	int x, y;
	for(int i = 1; i <= m; i++){
		scanf("%d%d", &x, &y);
		tj::add(x, y);
	}
	for(int i = 1; i <= n; i++){
		if(!tj::dfn[i]){
			tj::tarjan(i);
		}
	}
	if(tot == 1){
		cout << sz[1] << endl;
		return 0;
	}
	rebuild();
	spfa(root[1]);
	cout << dis[root[1]+tot] << endl;
	
	return 0;
}