Source code for submission s1056

Go to diff to previous submission

spider.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdint.h>
  5. #include <ctype.h>
  6. #include <math.h>
  7.  
  8. #include <string>
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <algorithm>
  13.  
  14. using namespace std;
  15.  
  16. typedef pair <int, int> PII;
  17. typedef long long int LL;
  18. typedef vector <int> VI;
  19. typedef vector <LL> VLL;
  20.  
  21. #define FOR(i, a, b) for ( int i = a; i < b; ++i )
  22. #define FORD(i, a, b) for ( int i = a-1; i >= 0; --i )
  23.  
  24. #define FILL(x, v, n) for ( int _i = 0; _i < n; ++_i ) x[_i] = v;
  25.  
  26. const int MAX_V = 2001;
  27. const int MAX_E = 1000005;
  28.  
  29. struct Edge
  30. {
  31.     int a, b;
  32.     LL w;
  33. };
  34.  
  35. int uf[ MAX_V ];
  36. Edge edge[ MAX_E ];
  37.  
  38. struct UnionFind
  39. {
  40.     int N, numSets;
  41.     void Init ( int n )
  42.     {
  43. 	N = n;
  44. 	numSets = N;
  45. 	FOR(i,0,N)
  46. 	    uf[ i ] = i;
  47.     }
  48.  
  49.     void Union ( int i, int j )
  50.     {
  51. 	if ( !IsSameSet( i, j ) )
  52. 	{
  53. 	    --numSets;
  54. 	    int fi = Find( i ), fj = Find( j );
  55. 	    uf[ fi ] = uf[ fj ];
  56. 	}
  57.     }
  58.     int Find ( int i ) { return (uf[i] == i) ? i : (uf[i] = Find(uf[i]) ); }
  59.     bool IsSameSet ( int i, int j ) { return Find( i ) == Find( j ); }
  60. };
  61.  
  62. bool Comp ( const Edge & a, const Edge & b )
  63. {
  64.     return a.w < b.w;
  65. }
  66.  
  67. int main()
  68. {
  69.     UnionFind u;
  70.     int N, M, maxID;
  71.     LL max;
  72.     while ( scanf( "%d %d", &N, &M ) == 2 )
  73.     {
  74. 	max = 0;
  75. 	FOR(i,0,M)
  76. 	{
  77. 	    scanf( "%d %d %lld", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w );
  78. 	    --edge[ i ].a;
  79. 	    --edge[ i ].b;
  80. 	    if ( edge[ i ].w > max )
  81. 	    {
  82. 		max = edge[ i ].w;
  83. 		maxID = i;
  84. 	    }
  85. 	}
  86. 	if ( M == 0 )
  87. 	{
  88. 	    printf( "disconnected\n" );
  89. 	    continue;
  90. 	}
  91.  
  92. 	edge[ maxID ].w = -edge[ maxID ].w;
  93. 	sort( edge, edge + M, Comp );
  94.  
  95. 	LL res = 0;
  96. 	u.Init( N );
  97. 	FOR(i,0,M)
  98. 	    if ( !u.IsSameSet( edge[ i ].a, edge[ i ].b ) )
  99. 	    {
  100. 		u.Union( edge[ i ].a, edge[ i ].b );
  101. 		res += edge[ i ].w;
  102. 		if ( u.numSets == 1 )
  103. 		    break;
  104. 	    }
  105. 	if ( u.numSets == 1 )
  106. 	    printf( "%lld\n", res );
  107. 	else
  108. 	    printf( "disconnected\n" );
  109.     }
  110.     return 0;
  111. }
  112.  

Diff to submission s1035

spider.cpp

--- c4.s1035.cteam004.spider.cpp.0.spider.cpp
+++ c4.s1056.cteam004.spider.cpp.0.spider.cpp
@@ -29,5 +29,6 @@
 struct Edge
 {
-    int a, b, w;
+    int a, b;
+    LL w;
 };
 
@@ -67,5 +68,6 @@
 {
     UnionFind u;
-    int N, M, max, maxID;
+    int N, M, maxID;
+    LL max;
     while ( scanf( "%d %d", &N, &M ) == 2 )
     {
@@ -73,5 +75,5 @@
         FOR(i,0,M)
         {
-            scanf( "%d %d %d", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w );
+            scanf( "%d %d %lld", &edge[ i ].a, &edge[ i ].b, &edge[ i ].w );
             --edge[ i ].a;
             --edge[ i ].b;
@@ -91,5 +93,5 @@
         sort( edge, edge + M, Comp );
 
-        int res = 0;
+        LL res = 0;
         u.Init( N );
         FOR(i,0,M)
@@ -102,5 +104,5 @@
             }
         if ( u.numSets == 1 )
-            printf( "%d\n", res );
+            printf( "%lld\n", res );
         else
             printf( "disconnected\n" );