1049 - One Way Roads

1049 - One Way Roads

Topic: DFS

concept: কস্টকে ডিরেক্টটেড ধরবো তারপর আনডিক্টটেড গ্রাফ এ ডিএফএস চালাবো.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int maxn = 105;
	vector<int>graph[maxn];
	int visited[maxn];
	int cost[maxn][maxn];
	int N,P;
	int test, flag;
	void dfs(int s)
	{
	//cout << "enter---\n";
	if(visited[s]) return;
	visited[s] = 1;
	for(int i = 0; i < graph[s].size(); i++)
	{
	int v = graph[s][i];
	if(!visited[v])
	{
	test++;
	//cout << s << "---->"<<v<<": "<<cost[s][v]<<endl;
	// visited[v] = 1;
	if(cost[s][v] > 0) P += cost[s][v];
	else N += cost[s][v];
	dfs(v);
	}
	else if(test >= 2 && v == 1 && flag == 0){
	if(cost[s][v] > 0) P += cost[s][v];
	else N += cost[s][v];
	flag++;
	}
	}
	}
	int main()
	{
	int T;
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs++)
	{
	int n,m;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
	graph[i].clear();
	visited[i] = 0;
	// cost[i][i] = 0;
	}
	for(int i = 0; i < n; i++)
	{
	int u,v,w;
	//cin >> u >> v >> w;
	scanf("%d %d %d", &u,&v,&w);
	graph[u].push_back(v);
	graph[v].push_back(u);
	cost[u][v] = w;
	cost[v][u] = -w;
	//cout << cost[u][v] << " -------- "<<cost[v][u]<<endl;
	}
	N = 0, P = 0;
	test=0, flag = 0;
	dfs(1);
	//cout << N << " "<<P << endl;
	printf("Case %d: %d\n", cs, min(abs(N), P));
	}
	return 0;
	}

view raw One Way Roads.cpp hosted with ❤ by GitHub

Share: