Go to diff to previous submission
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #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; #define INF 1000000014 map<int, int> p; int n, c, f, s, t, adj[1014][1014], deg[1014], max_flow; vector<int> nodes[1014]; 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 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); } return 0; }
--- c5.s541.cteam011.fr.cpp.0.fr.cpp +++ c5.s712.cteam011.fr.cpp.0.fr.cpp @@ -24,5 +24,5 @@ #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; -#define INF 2000000014 +#define INF 1000000014 map<int, int> p; @@ -60,13 +60,22 @@ 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]; - nodes[to].PB(from); - adj[to][from] = weight; - ++deg[to]; + if (from != c) + { + nodes[to].PB(from); + adj[to][from] = weight; + ++deg[to]; + } } s = c; - FOR(i, 1, n + 1) if (deg[i] == 1) + FOR(i, 1, n + 1) if (deg[i] <= 1) { nodes[i].PB(1009);