yukicoder : No.2914 正閉路検出

これは割とすんなり。
https://yukicoder.me/problems/no/2914

問題

無向グラフが与えられる。
各辺には向きがあり、順方向に移動すると辺に設定された満足度が加算されるが、逆向きに移動すると減算される。

このグラフの閉路のうち、合計満足度が正となるものがあれば答えよ。

解法

連結成分毎に、適当に1頂点からDFS順に探索し、満足度の合計が0でない閉路を求めよう。
満足度の合計が正なら、その閉路が解だし、負なら逆向きの閉路を答えればよい。

int N,M;
vector<vector<int>> E[101010];
ll dp[101010];
vector<pair<int,int>> P;

void dfs(int cur,ll v) {
	
	if(dp[cur]==-1LL<<60) {
		dp[cur]=v;
		FORR(e,E[cur]) {
			P.push_back({e[0],e[2]});
			dfs(e[0],v+e[1]);
			P.pop_back();
		}
	}
	else if(dp[cur]!=v) {
		vector<int> A;
		int ok=0;
		FORR(a,P) {
			if(ok) A.push_back(a.second);
			if(a.first==cur) ok=1;
		}
		if(dp[cur]>v) reverse(ALL(A));
		cout<<A.size()<<endl;
		cout<<cur+1<<endl;
		FORR(a,A) {
			cout<<a;
			if(a!=A.back()) cout<<" ";
		}
		cout<<endl;
		exit(0);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>k;
		x--,y--;
		E[x].push_back({y,k,i+1});
		E[y].push_back({x,-k,i+1});
	}
	FOR(i,N) dp[i]=-1LL<<60;
	FOR(i,N) if(dp[i]==-1LL<<60) {
		P.push_back({i,0});
		dfs(i,0);
		P.pop_back();
	}
	cout<<-1<<endl;
}

まとめ

こちらは割と素直。