[TIOJ] 1142. 3.關鍵邏輯閘

題目連結:http://tioj.infor.org/problems/1142

---

笨笨的我完全想不出來該怎麼寫...最後是被雷了才知道的QAQ。不過明顯有幾個點大家應該早就知道，本題其實就是要找最長路，並且看該路上有幾個節點，且如果有兩個人權重相同，則兩個人都要走，因此不妨先求出走到每個點所要花的時間，再從最大的開始dfs回去，這裡為了方便，弄了一個假節點，與所有點連接，這樣比較方便在dfs回去時看誰最大

#include <bits/stdc++.h>
using namespace std;
#define N 100000
#define PB push_back

int val[N+5], deg[N+5], valSm[N+5], cnt=0;
vector<int> graph[N+5], rgraph[N+5];
bitset<N+5> visited;

void dfs(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>val[i];
		valSm[i]=val[i];
	}
	for(int i=0;i<m;i++){
		int st, ed;cin>>st>>ed;
		deg[ed]++;
		graph[st].PB(ed);
		rgraph[ed].PB(st);
	}
	for(int i=1;i<=n;i++) rgraph[N+2].PB(i);
	queue<int> qq;
	for(int i=1;i<=n;i++)
		if(deg[i]==0) qq.push(i);
	while(!qq.empty()){
		int tp=qq.front();qq.pop();
		for(auto i:graph[tp]){
			deg[i]--;
			if(deg[i]==0) qq.push(i);
			valSm[i]=max(valSm[i], valSm[tp]+val[i]);
		}
	}
	dfs(N+2);
	cout<<(cnt-1)<<'\n';
	return 0;
}

void dfs(int id){
	if(visited[id])return;
	visited[id]=1;
	cnt++;
	vector<int> mx;
	for(auto i:rgraph[id]){
		if(mx.empty() || valSm[i]>valSm[mx[0]]){
			mx.clear();
			mx.PB(i);
		}else if(!mx.empty()&&valSm[i]==valSm[mx[0]]){
			mx.PB(i);
		}
	}
	for(auto i:mx) dfs(i);
}