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; }
--- 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; }