CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }  

POJ.2186 Popular Cows

1.Problem
2186 -- Popular Cows (poj.org)

2.Idea
SCC+Topological Sort

3.Source

 const int N = 100005;  
 //////////////////////////////  
 int V;  
 vector<int> G[N];  
 vector<int> rG[N];  
 vector<int> vs;  
 bool used[N];  
 int cmp[N];  
 void add_edge(int from, int to)  
 {  
      G[from].push_back(to);  
      rG[to].push_back(from);  
 }  
 void dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           if (!used[G[v][i]]) dfs(G[v][i]);  
      }  
      vs.push_back(v);  
 }  
 void rdfs(int v, int k)  
 {  
      used[v] = true;  
      cmp[v] = k;  
      for (int i = 0; i < rG[v].size(); i++) {  
           if (!used[rG[v][i]]) rdfs(rG[v][i], k);  
      }  
 }  
 int scc()  
 {  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) dfs(v);  
      }  
      memset(used, 0, sizeof used);  
      int k = 0;  
      for (int i = vs.size() - 1; i >= 0; i--) {  
           if (!used[vs[i]]) rdfs(vs[i], k++);  
      }  
      return k;  
 }  
 int n, m;  
 int a[N], b[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &m);  
      REP(i, m) scanf("%d%d", &a[i], &b[i]);  
      V = n;  
      for (int i = 0; i < m; i++) {  
           add_edge(a[i] - 1, b[i] - 1);  
      }  
      int nn = scc();  
      int u = 0, num = 0;  
      for (int v = 0; v < V; v++) {  
           if (cmp[v] == nn - 1) {  
                u = v;  
                num++;  
           }  
      }  
      memset(used, 0, sizeof(used));  
      rdfs(u, 0);  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) {  
                num = 0;  
                break;  
           }  
      }  
      printf("%d\n", num);  
 }  

POJ.1145 Tree Summing

1.Problem
http://poj.org/problem?id=1145

2.Idea
Tree pre-order traversing

3.Source

 int tree_sum(int n)  
 {  
      int ans = 0, m;  
      if (scanf(" (%d", &m)) {  
           ans = tree_sum(n - m) + tree_sum(n - m);  
           if (ans < 2) ans = 0;  
      }  
      else  
           ans = !n;  
      scanf(" )");  
      return ans;  
 }  
 int main()  
 {  
      int n;  
      while (scanf("%d", &n) != EOF) {  
           if (tree_sum(n)) printf("yes\n");  
           else printf("no\n");  
      }  
      return 0;  
 }  

POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }  

POJ.1330 Nearest Common Ancestors

1.Problem
http://poj.org/problem?id=1330

2.Idea
while(x!=y) {
     if(depth x < depth y) y = parent of y;
     else  x = parent of x;
}

3.Source

 const int N = 10000;  
 vector<int> a[N]; // multiple linked list, the list of children for node i is a vector  
 int f[N], r[N]; // representations of parents and hierarchy, the parent and hierarchy for node i is f[i] and r[i]  
 void DFS(int u, int dep) // Pre-order Traversal from node u  
 {  
      r[u] = dep; // node u is at hierarchy dep  
      for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it)  
           DFS(*it, dep + 1);// Recursion for every child of u  
 }  
 int main()  
 {  
      int casenum, num, n, i, x, y;  
      scanf("%d", &casenum); // number of test cases  
      for (num = 0; num < casenum; num++)  
      {  
           scanf("%d", &n); // number of nodes  
           for (i = 0; i < n; i++) a[i].clear(); //initialization  
           memset(f, 255, sizeof(f));  
           for (i = 0; i < n - 1; i++)  
           {  
                scanf("%d %d", &x, &y); // edge (x, y)  
                a[x - 1].push_back(y - 1); // push node (y-1) into the list of (x - 1)’s children  
                f[y - 1] = x - 1; //node(y-1)’s parent is (x-1)  
           }  
           for (i = 0; f[i] >= 0; i++); // search the root i  
           DFS(i, 0); // calculate every nodes’ hierarchy from the root  
           scanf("%d %d", &x, &y); // a pair of nodes  
           x--; y--;  
           while (x != y) // to find the Nearest Common Ancestors  
           {  
                if (r[x]>r[y]) x = f[x];  
                else y = f[y];  
           }  
           printf("%d\n", x + 1);// Output  
      }  
      return 0;  
 }  

CodeForces. 1337C Linova and Kingdom

1.Problem
https://codeforces.com/contest/1337/problem/C

2.Idea
Sort by {Depth - Child Number}, and pick k vertices.

3.Source

 int n, k;  
 vector<int> adj[N];  
 int dist[N];  
 bool visited[N];  
 int child[N];  
 bool col[N];  
 int dist2[N];  
 struct City {  
      int num, child, dist;  
      bool operator < (const City &a)const {  
           return dist - child < a.dist - a.child;  
      }  
 } Cities[N];  
 void getChild(int k)  
 {  
      //cout << k << endl;  
      visited[k] = true;  
      for (int i = 0; i < adj[k].size(); i++) {  
           int u = adj[k][i];  
           if (visited[u] == 0) {  
                getChild(u);  
                child[k] += (1 + child[u]);  
           }  
      }  
 }  
 void colorCities()  
 {  
      for (int i = 0; i < n; i++) {  
           Cities[i].num = i;  
           Cities[i].child = child[i];  
           Cities[i].dist = dist[i];  
      }  
      sort(Cities, Cities + n);  
      for (int i = 0; i < n - k; i++) {  
           int t = Cities[i].num;  
           col[t] = true;  
      }  
 }  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 0; i < n - 1; i++) {  
           int u, v;  
           cin >> u >> v;  
           u--; v--;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      // get dist  
      memset(visited, 0, sizeof visited);  
      queue<P> q;  
      q.push(P(0, 0));  
      while (!q.empty()) {  
           int v = q.front().first;  
           int d = q.front().second;  
           q.pop();  
           visited[v] = 1;  
           dist[v] = d;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0 && dist[u] == 0) {  
                     q.push(P(u, d + 1));  
                }  
           }  
      }  
      //get child  
      memset(visited, 0, sizeof visited);  
      getChild(0);  
      //color  
      colorCities();  
      //count  
      memset(visited, 0, sizeof visited);  
      queue<P> q1;  
      q1.push(P(0, 0));  
      while (!q1.empty()) {  
           int v = q1.front().first;  
           int d = q1.front().second;  
           q1.pop();  
           visited[v] = 1;  
           dist2[v] = d;  
           if (col[v]) d++;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0) {  
                     q1.push(P(u, d));  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (col[i] == 0) ans += dist2[i];  
      }  
      cout << ans << endl;  
      return 0;  
 }  

CodeForces. 1339D Edge Weight Assignment

1.Problem.
https://codeforces.com/contest/1339/problem/D

2.Idea
Here

3.Source

 vector<int> adj[N];  
 int d[N];  
 set<int> st;  
 // calc dist from root  
 void dfs(int v, int p)  
 {  
      for (auto& x : adj[v]) {  
           if (x == p) continue;  
           d[x] = d[v] + 1;  
           dfs(x, v);  
      }  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      for (int i = 1; i < n; i++) {  
           int v, u;  
           cin >> v >> u;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      int root = 0;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                root = i;  
                break;  
           }  
      }  
      dfs(root, 0);  
      int mn = 1, mx = n - 1;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                if (d[i] % 2 != 0) {  
                     mn = 3;  
                }  
                st.insert(adj[i][0]);  
                --mx;  
           }  
      }  
      mx += st.size();  
      cout << mn << " " << mx << endl;  
      return 0;  
 }  

POJ.3411 Paid Roads

1.Problem
http://poj.org/problem?id=3411

2.Idea
bit DP + Bellman-Ford

3.Source

 #define MAX_N 10  
 #define MAX_M 10  
 struct Edge {  
      int a, b, c, p, r;  
 } Edges[MAX_M];  
 int dp[1 << MAX_N][MAX_N];  
 int n, m;  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < m; i++) {  
           cin >> Edges[i].a >> Edges[i].b >> Edges[i].c >> Edges[i].p >> Edges[i].r;  
           Edges[i].a--;  
           Edges[i].b--;  
           Edges[i].c--;  
      }  
      for (int i = 0; i < 1 << MAX_N; i++) {  
           fill(dp[i], dp[i] + MAX_N, INF);  
      }  
      dp[1][0] = 0;  
      bool update;  
      while (1) {  
           update = false;  
           for (int _ = 0; _ < n; _++) {  
                for (int i = 0; i < m; i++) {  
                     int a = Edges[i].a, b = Edges[i].b, c = Edges[i].c, p = Edges[i].p, r = Edges[i].r;  
                     for (int S = 0; S < 1 << n; S++) {  
                          if ((S & (1 << a)) && dp[S][a] < INF) {  
                               if (dp[S | (1 << b)][b] > dp[S][a] + r) {  
                                    update = true;  
                                    dp[S | (1 << b)][b] = dp[S][a] + r;  
                               }  
                               if ((S & (1 << c))) {  
                                    if (dp[S | (1 << b)][b] > dp[S][a] + p) {  
                                         update = true;  
                                         dp[S | (1 << b)][b] = dp[S][a] + p;  
                                    }  
                               }  
                          }  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      int ans = INF;  
      for (int S = 0; S < 1 << n; S++) {  
           ans = min(ans, dp[S][n - 1]);  
      }  
      if (ans == INF) {  
           cout << "impossible" << endl;  
      }  
      else {  
           cout << ans << endl;  
      }  
      return 0;  
 }  

POJ.3268 Silver Cow Party

1.Problem
http://poj.org/problem?id=3268

2.Idea
From X to arbitrary node: Using Dijkstra algorithm
From arbitrary node to X: Reverse all edges direction, and using Dijkstra too.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int from, to, cost; } es[MAX_E];  
 int V, E, X;  
 int cost[MAX_V][MAX_V];  
 int d[MAX_V];  
 int d1[MAX_V];  
 bool used[MAX_V];  
 void dijkstra(int s)  
 {  
      fill(d, d + V, INF);  
      fill(used, used + V, false);  
      d[s] = 0;  
      while (true) {  
           int v = -1;  
           for (int u = 0; u < V; u++) {  
                if (!used[u] && (v == -1 || d[v] > d[u])) v = u;  
           }  
           if (v == -1) break;  
           used[v] = true;  
           for (int u = 0; u < V; u++) {  
                d[u] = min(d[u], d[v] + cost[v][u]);  
           }  
      }  
 }  
 int main()  
 {  
      cin >> V >> E >> X;  
      X--;  
      for (int i = 0; i < V; i++)  
           for (int j = 0; j < V; j++) {  
                if (i == j) cost[i][j] = 0;  
                else cost[i][j] = INF;  
           }  
      for (int i = 0; i < E; i++) {  
           int a, b, t;  
           cin >> a >> b >> t;  
           a--;  
           b--;  
           cost[a][b] = t;  
      }  
      dijkstra(X);  
      for (int i = 0; i < V; i++) d1[i] = d[i];  
      for (int i = 0; i < V; i++)  
           for (int j = i + 1; j < V; j++) {  
                swap(cost[i][j], cost[j][i]);  
           }  
      dijkstra(X);  
      int ans = 0;  
      for (int i = 0; i < V; i++) {  
           ans = max(ans, d1[i] + d[i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ. Wormholes

1.Problem
http://poj.org/problem?id=3259

2.Idea
Using Bellman-Ford algorithm to detect negative loop in the graph.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int from, to, cost; } es[MAX_E];  
 int V, E;  
 int d[MAX_V];  
 bool find_negative_loop() //Bellman-Ford  
 {  
      memset(d, 0, sizeof d);  
      for (int i = 0; i < V; i++) {  
           for (int j = 0; j < E; j++) {  
                edge e = es[j];  
                if (d[e.to] > d[e.from] + e.cost) {  
                     d[e.to] = d[e.from] + e.cost;  
                     if (i == V - 1) return true;  
                }  
           }  
      }  
      return false;  
 }  
 int main()  
 {  
      int t;  
      int x, y, z, cnt = 0;  
      cin >> t;  
      while (t--) {  
           int n, m, w;  
           cin >> n >> m >> w;  
           V = n;  
           E = m * 2 + w;  
           cnt = 0;  
           for (int i = 0; i < m; i++) {  
                cin >> x >> y >> z;  
                x--; y--;  
                es[cnt].from = x;  
                es[cnt].to = y;  
                es[cnt].cost = z;  
                cnt++;  
                es[cnt].to = x;  
                es[cnt].from = y;  
                es[cnt].cost = z;  
                cnt++;  
           }  
           for (int i = 0; i < w; i++) {  
                cin >> x >> y >> z;  
                x--; y--;  
                es[cnt].from = x;  
                es[cnt].to = y;  
                es[cnt].cost = -z;  
                cnt++;  
           }  
           if (find_negative_loop()) cout << "YES" << endl;  
           else cout << "NO" << endl;  
      }  
      return 0;  
 }  

POJ.2395 Out of Hay

1.Problem
http://poj.org/problem?id=2395

2.Idea
Minimum Spanning Tree.

3.Source

 #define MAX_E 10004  
 #define MAX_V 2003  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      int res = -1;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res = max(res, e.cost);  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      cin >> V >> E;  
      for (int j = 0; j < E; j++) {  
           cin >> es[j].v >> es[j].u >> es[j].cost;  
      }  
      cout << kruskal() << endl;  
      return 0;  
 }  

POJ.2377 Bad Cowtractors

1.Problem
http://poj.org/problem?id=2377

2.Idea
Get maximum spanning tree by Kruskal algorithm.

3.Source

 #define MAX_E 20004  
 #define MAX_V 1011  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost > e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      ll res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += (ll)e.cost;  
           }  
      }  
      set<int> st;  
      for (int i = 0; i < V; i++) {  
           st.insert(find_set(i));  
      }  
      if (st.size() > 1) return -1;  
      return res;  
 }  
 int main()  
 {  
      cin >> V >> E;  
      for (int j = 0; j < E; j++) {  
           cin >> es[j].v >> es[j].u >> es[j].cost;  
      }  
      cout << kruskal() << endl;  
      return 0;  
 }  

POJ.1258 Agri-Net

1.Problem
http://poj.org/problem?id=1258

2.Idea
Minimum Spanning Tree.

3.Source

 #define MAX_E 20004  
 #define MAX_V 111  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      ll res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += e.cost;  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      int tmp;  
      while (cin >> V) {  
           E = 0;  
           for (int i = 0; i < V; i++)  
                for (int j = 0; j < V; j++) {  
                     cin >> tmp;  
                     if (i < j) {  
                          es[E].u = i;  
                          es[E].v = j;  
                          es[E].cost = tmp;  
                          E++;  
                     }  
                }  
           cout << kruskal() << endl;  
      }  
      return 0;  
 }  

POJ.3723 Conscription

1.Problem
http://poj.org/problem?id=3723

2.Idea
Calculating the minimum cost by Kruskal algorithm.

3.Source

 #define MAX_R 50004  
 #define MAX_V 20003  
 struct edge { int u, v, cost; };  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int N, M, R, V, E;  
 edge es[MAX_R];  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      int res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += e.cost;  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> N >> M >> R;  
           V = N + M;  
           E = R;  
           for (int i = 0; i < R; i++) {  
                scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].cost);  
                es[i].v += N;  
                es[i].cost *= -1;  
           }  
           cout << 10000 * V + kruskal() << endl;  
      }  
      return 0;  
 }  

POJ.3169 Layout

1.Problem
http://poj.org/problem?id=3169

2.Idea
This problem is a special case of "Linear programming", which can be solved by graph shortest path problem. Here, Bellman-Ford method is used.

3.Source

 #define MAX_ML 10004  
 #define MAX_MD 10004  
 #define MAX_N 1003  
 int N, ML, MD;  
 int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];  
 int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];  
 int d[MAX_N];  
 void solve()  
 {  
      fill(d, d + N, INF);  
      d[0] = 0;  
      for (int k = 0; k < N; k++) {  
           for (int i = 0; i + 1 < N; i++) {  
                if (d[i + 1] < INF) d[i] = min(d[i], d[i + 1]);  
           }  
           for (int i = 0; i < ML; i++) {  
                if (d[AL[i] - 1] < INF) d[BL[i] - 1] = min(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);  
           }  
           for (int i = 0; i < MD; i++) {  
                if (d[BD[i] - 1] < INF) d[AD[i] - 1] = min(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);  
           }  
      }  
      int res = d[N - 1];  
      if(d[0] < 0) {  
           res = -1;  
      }  
      else if (res == INF) {  
           res = -2;  
      }  
      cout << res << endl;  
 }  
 int main()  
 {  
      cin >> N >> ML >> MD;  
      for (int i = 0; i < ML; i++) {  
           cin >> AL[i] >> BL[i] >> DL[i];  
      }  
      for (int i = 0; i < MD; i++) {  
           cin >> AD[i] >> BD[i] >> DD[i];  
      }  
      solve();  
      return 0;  
 }  

POJ. 2139 Six Degrees of Cowvin Bacon

1.Problem
http://poj.org/problem?id=2139

2.Idea
Calculate all distance between 2 nodes by Warshall-Floyd.

3.Source:

 
 int n, m;  
 int d[333][333];  
 void solve()  
 {  
      //fill(d, d + 333 * 333, INF);  
      for (int k = 0; k < n; k++)  
           for (int i = 0; i < n; i++)  
                for (int j = 0; j < n; j++) {  
                     d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  
                }  
      int ans = INF;  
      for (int i = 0; i < n; i++) {  
           int sum = 0;  
           for (int j = 0; j < n; j++) {  
                sum += d[i][j];  
           }  
           ans = min(ans, sum * 100 / (n - 1));  
      }  
      cout << ans << endl;  
 }  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++) {  
                if (i == j) d[i][j] = 0;  
                else d[i][j] = INF;  
           }  
      for (int i = 0; i < m; i++) {  
           int k;  
           cin >> k;  
           int x[333];  
           for (int j = 0; j < k; j++) {  
                cin >> x[j];  
                x[j]--;  
           }  
           for (int i = 0; i < k; i++)   
                for (int j = i + 1; j < k; j++) {  
                     d[x[i]][x[j]] = d[x[j]][x[i]] = 1;  
                }  
      }  
      solve();  
      return 0;  
 }  

POJ.3255 Roadblocks

1.Problem
http://poj.org/problem?id=3255

2.Idea
Using 2 arrays for the shortest and the second shortest paths while updating by Dijkstra.

3.Source

 #define MAX_N 5000  
 struct edge { int to, cost; };  
 int N, R;  
 vector<edge> G[MAX_N];  
 int dist[MAX_N];  
 int dist2[MAX_N];  
 void solve()  
 {  
      priority_queue<P, vector<P>, greater<P>> que;  
      fill(dist, dist + N, INF);  
      fill(dist2, dist2 + N, INF);  
      dist[0] = 0;  
      que.push(P(0, 0));  
      while (!que.empty()) {  
           P p = que.top(); que.pop();  
           int v = p.second, d = p.first;  
           if (dist2[v] < d) continue;  
           for (int i = 0; i < G[v].size(); i++) {  
                edge e = G[v][i];  
                int d2 = d + e.cost;  
                if (dist[e.to] > d2) {  
                     swap(dist[e.to], d2);  
                     que.push(P(dist[e.to], e.to));  
                }  
                if (dist2[e.to] > d2 && dist[e.to] < d2) {  
                     dist2[e.to] = d2;  
                     que.push(P(dist2[e.to], e.to));  
                }  
           }  
      }  
      cout << dist2[N - 1] << endl;  
 }  
 int main()  
 {  
      cin >> N >> R;  
      for (int i = 0; i < R; i++) {  
           int a, b, d;  
           cin >> a >> b >> d;  
           a--;  
           b--;  
           edge e1; e1.to = b; e1.cost = d;  
           edge e2; e2.to = a; e2.cost = d;  
           G[a].push_back(e1);  
           G[b].push_back(e2);  
      }  
      solve();  
      return 0;  
 }