Source code for submission s844

Go to diff to previous submission

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>
 
using namespace std;
 
#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
 
#define PB push_back
#define MP make_pair
 
#define MM(co, cim) memset((co), (cim), sizeof((co)))
 
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
 
int g[1007][1007];
int gv[1007][1007];
int gc[1007];
int inf = 2000000000;
 
int DFS2(int v, int sum1, int par) {
	int sum2 = 0;
	if(gc[v] == 1) return sum1;
	FOR(i,0,gc[v]) {
		if(g[v][i] == par) continue;
		sum2 += DFS2(g[v][i], gv[v][i], v);
	}
	return min(sum1, sum2);
}
 
int DFS(int v) {
	int sum = 0;
	FOR(i,0,gc[v]) {
		sum += DFS2(g[v][i], gv[v][i], v);
	}
	return sum;
}
 
int main ()
{
 
	int n,c;
	int a,b,v;
	while(scanf("%d%d", &n, &c) == 2) {
		FOR(i,1,n+1) gc[i] = 0;
		FOR(k,0,n-1) {
			scanf("%d%d%d", &a, &b, &v);
			g[a][gc[a]] = b;
			gv[a][gc[a]++] = v;
			g[b][gc[b]] = a;
			gv[b][gc[b]++] = v;
 
		}
		printf("%d\n", DFS(c));
	}
 
  return 0;
}
 

Diff to submission s712

--- c5.s712.cteam011.fr.cpp.0.fr.cpp
+++ c5.s844.cteam011.fr.cpp.0.fr.cpp
@@ -3,5 +3,4 @@
 #include <cstdio>
 #include <cstdlib>
-#include <cstring>
 #include <iostream>
 #include <sstream>
@@ -24,90 +23,45 @@
 #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
 
-#define INF 1000000014
+int g[1007][1007];
+int gv[1007][1007];
+int gc[1007];
+int inf = 2000000000;
 
-map<int, int> p;
-int n, c, f, s, t, adj[1014][1014], deg[1014], max_flow;
-vector<int> nodes[1014];
+int DFS2(int v, int sum1, int par) {
+        int sum2 = 0;
+        if(gc[v] == 1) return sum1;
+        FOR(i,0,gc[v]) {
+                if(g[v][i] == par) continue;
+                sum2 += DFS2(g[v][i], gv[v][i], v);
+        }
+        return min(sum1, sum2);
+}
 
-void augmentPath (int v, int minEdge)
-{
-  if (v == s)
-  {
-    f = minEdge;
-    return;
-  }
-  else if (p.count(v))
-  {
-    augmentPath(p[v], min(minEdge, adj[p[v]][v]));
-    adj[p[v]][v] -= f;
-    adj[v][p[v]] += f;
-  }  
+int DFS(int v) {
+        int sum = 0;
+        FOR(i,0,gc[v]) {
+                sum += DFS2(g[v][i], gv[v][i], v);
+        }
+        return sum;
 }
 
 int main ()
 {
-  while (scanf("%d%d", &n, &c) == 2)
-  {
-    p.clear();
-    MM(deg, 0);
-    FOR(i, 0, 1014) 
-    {
-      nodes[i].clear();
-      MM(adj[i], 0);
-    }
-    FOR(i, 0, n - 1)
-    {
-      int from, to, weight;
-      scanf("%d%d%d", &from, &to, &weight);
-      if (to == c)
-      {
-        int tmp = from;
-        from = to;      
-        to = tmp;
-      }
-      nodes[from].PB(to);
-      adj[from][to] = weight;
-      ++deg[from];
-      if (from != c)
-      {
-        nodes[to].PB(from);
-        adj[to][from] = weight;
-        ++deg[to];
-      }
-    }
-    s = c;
-    FOR(i, 1, n + 1) if (deg[i] <= 1)
-    {
-      nodes[i].PB(1009);
-      adj[i][1009] = INF;
-    }
-    t = 1009;
-    max_flow = 0;
-    while (1)
-    {
-      f = 0;
-      queue<int> q; map<int, int> dist;
-      q.push(s); dist[s] = 0;
-      while (!q.empty())
-      {
-        int u = q.front(); q.pop();
-        if (u == t) break;
-        vector<int>::iterator v;
-        for (v = nodes[u].begin(); v != nodes[u].end(); v++)
-        {
-          if (adj[u][*v] > 0 && !dist.count(*v))
-          {
-            dist[*v] = dist[u] + 1;
-            q.push(*v);
-            p[*v] = u;
-          }
-        }
-      }
-      augmentPath(t, INF);
-      if (f == 0) break;
-      max_flow += f;    
-    }
-    printf("%d\n", max_flow);
-  }
+
+        int n,c;
+        int a,b,v;
+        while(scanf("%d%d", &n, &c) == 2) {
+                FOR(i,1,n+1) gc[i] = 0;
+                FOR(k,0,n-1) {
+                        scanf("%d%d%d", &a, &b, &v);
+                        g[a][gc[a]] = b;
+                        gv[a][gc[a]++] = v;
+                        g[b][gc[b]] = a;
+                        gv[b][gc[b]++] = v;
+                        
+                }
+                printf("%d\n", DFS(c));
+        }
+  
   return 0;
 }