Source code for submission s953

Go to diff to previous submission

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
 
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////
 
const int MAX = 2007;
int N, M;
int parent[MAX];
 
int get(int n)
{
  return parent[n] = (n == parent[n] ? n : get(parent[n]));
}
 
bool joined(int a, int b)
{
  a = get(a);
  b = get(b);
  return a == b;
}
 
void join(int a, int b)
{
  a = get(a);
  b = get(b);
  parent[a] = b;
}
 
struct Edge
{
  int a, b, c;
  bool operator<(const Edge & e) const { return c < e.c; }
} edges[1000000];
 
vector<pair<int, int> > tree[MAX];
int dist[MAX][MAX];
 
void go(int root, int node, int parent, int best)
{
  dist[root][node] = best;
  REP(i, tree[node].size())
  {
   int next = tree[node][i].first, c = tree[node][i].second;
   if (next != parent)
     go(root, next, node, max(best, c));
  }
}
 
int main()
{
  while (scanf("%d%d", &N, &M) == 2)
  {
    REP(i, N)
    {
      parent[i] = i;
      tree[i].clear();
    }
 
    REP(i, M)
    {
	scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c);
	--edges[i].a;
	--edges[i].b;
    }
    sort(edges, edges+M);
 
    int used = 0, sum = 0;
    REP(i, M)
      if (!joined(edges[i].a, edges[i].b))
      {
	join(edges[i].a, edges[i].b);
	sum += edges[i].c;
	++used;
	tree[edges[i].a].push_back(make_pair(edges[i].b, edges[i].c));
	tree[edges[i].b].push_back(make_pair(edges[i].a, edges[i].c));
      }
    if (used != N-1)
    {
      printf("disconnected\n");
      continue;
    }
 
    REP(i, N) go(i, i, -1, 0);
    int result = 1000000000;
    REP(i, M)
    {
	int a = edges[i].a, b = edges[i].b;
	result = min(result, sum-dist[a][b]-edges[i].c);
    }
    printf("%d\n", result);
  }
  return 0;
}
 

Diff to submission s587

--- c4.s587.cteam052.spider.cpp.0.spider.cpp
+++ c4.s953.cteam052.spider.cpp.0.spider.cpp
@@ -57,9 +57,28 @@
 } edges[1000000];
 
+vector<pair<int, int> > tree[MAX];
+int dist[MAX][MAX];
+
+void go(int root, int node, int parent, int best)
+{
+  dist[root][node] = best;
+  REP(i, tree[node].size())
+  {
+   int next = tree[node][i].first, c = tree[node][i].second;
+   if (next != parent)
+     go(root, next, node, max(best, c));
+  }
+}
+
 int main()
 {
   while (scanf("%d%d", &N, &M) == 2)
   {
-    REP(i, N) parent[i] = i;
+    REP(i, N)
+    {
+      parent[i] = i;
+      tree[i].clear();
+    }
+    
     REP(i, M)
     {
@@ -70,25 +89,28 @@
     sort(edges, edges+M);
     
-    int used = 0, result = 0;
-    if (M)
-    {
-      result -= edges[M-1].c;
-      join(edges[M-1].a, edges[M-1].b);
-      ++used;
-    }
-    REP(i, M-1)
-    {
+    int used = 0, sum = 0;
+    REP(i, M)
       if (!joined(edges[i].a, edges[i].b))
       {
         join(edges[i].a, edges[i].b);
-        result += edges[i].c;
+        sum += edges[i].c;
         ++used;
+        tree[edges[i].a].push_back(make_pair(edges[i].b, edges[i].c));
+        tree[edges[i].b].push_back(make_pair(edges[i].a, edges[i].c));
       }
-    }
-    
     if (used != N-1)
+    {
       printf("disconnected\n");
-    else
-      printf("%d\n", result);
+      continue;
+    }
+    
+    REP(i, N) go(i, i, -1, 0);
+    int result = 1000000000;
+    REP(i, M)
+    {
+        int a = edges[i].a, b = edges[i].b;
+        result = min(result, sum-dist[a][b]-edges[i].c);
+    }
+    printf("%d\n", result);
   }
   return 0;