Lightoj 1049 - One Way Roads

/*
The graph is a ring. Consider the third test case:
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
If we make a graph from these data, it will be look like the following:
1 --> 5 --> 3 <-- 2 --> 4 --> 6 <-- 1
and 2, 4 connected together.

You can easily decompose the edges in the two different directions:

1. Edges which goes to the left:
3 <-- 2     23
6 <-- 1        16

Total cost: 39

2. Edges which goes to the right:
1 --> 5         4
5 --> 3         8
2 --> 4        15
4 --> 6        42

Total cost: 69

Remember, 'left' or 'right' is not important here, you can easily build a graph with left
and right altered. All we care is the two different direction of the edges.
Choose the direction in which cost is minimum (here, left, cost is 39). And build
roads in the opposite direction. So in this case you have to built two roads,
3 --> 2
6 --> 1

Look, now you can go from any city to another city!
The question is now, how to build this graph?
Again, look at the test case. The first edge is 1 --> 5. You can place 5 either left or right of 1.

1 --> 5 or
5 <-- 1

Both left and right of 1 & 5 is empty, so it's entirely up to you what will you choose.
Say, you choose the first option, you place 5 to the right of 1 (1 --> 5).
Now the second edge, 5 --> 3. You must place 3 right of 5, because left of 5 is already filled
by 1.
1 --> 5 --> 3
So all you need to do is keep track of whether the right or left of a node has already been filled,
and adding new edges accordingly.


====== Thanks to Rafi Kamal vaiya ============

*/


#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 150;

int Right[high], Left[high];

int main()
{
    int N , test , tc=0 , i , a , b , c;
    sf("%d", &test);
    while(test--)
    {
        mset(Right , 0);
        mset(Left , 0);

        sf("%d", &N);

        int weightRight = 0 , weightLeft = 0;

        while(N--)
        {
            sf("%d %d %d", &a , &b , &c);

            if(!Right[a] && !Left[b]) // if a --> b, for this you have check weather right of 'a' and left of 'b' is empty or not
            {
                weightRight += c;
                Right[a] = 1;
                Left[b] = 1;
            }

            else // for b <-- a
            {
                weightLeft += c;

                Left[a] = 1;
                Right[b] = 1;
            }
        }

        pf("Case %d: %d\n" , ++tc , min(weightLeft , weightRight));
    }

    return 0;
}