fr.cpp
#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 2000000014
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)
{
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);
nodes[from].PB(to);
adj[from][to] = weight;
++deg[from];
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;
}