1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
struct edge_type {
	int to, next;
} edge[2333333];
int cnte = 1, h[2333333];
bool vis[2333333];
void ins(int x, int y) {
	edge[++cnte].to = y;
	edge[cnte].next = h[x];
	h[x] = cnte;
	edge[++cnte].to = x;
	edge[cnte].next = h[y];
	h[y] = cnte;
}
int h1, h2, fa[2333333];
void dfs(int now, int father) {
	vis[now] = true; fa[now] = father;
	for (int i = h[now]; i; i = edge[i].next) {
		if (edge[i].to == father) continue;
		if (vis[edge[i].to]) {
			if (fa[edge[i].to] != now) {
				h1 = edge[i].to;
				h2 = now;
			}
			continue;
		}
		dfs(edge[i].to, now);
	}
}
LL F[2333333][2], v[2333333];
void dfs1(int now, int father, int h1, int h2) {
	F[now][1] = v[now]; F[now][0] = 0;
	for (int i = h[now]; i; i = edge[i].next) {
		if (edge[i].to == father) continue;
		if ((now == h1 && edge[i].to == h2) || (now == h2 && edge[i].to == h1)) continue;
		dfs1(edge[i].to, now, h1, h2);
		F[now][0] += max(F[edge[i].to][0], F[edge[i].to][1]);
		F[now][1] += F[edge[i].to][0];
	}
}
bool v2[2333333];
void dfs2(int now) {
	v2[now] = true;
	F[now][1] = v[now]; F[now][0] = 0;
	for (int i = h[now]; i; i = edge[i].next) {
		if (v2[edge[i].to]) continue;
		dfs2(edge[i].to);
		F[now][0] += max(F[edge[i].to][0], F[edge[i].to][1]);
		F[now][1] += F[edge[i].to][0];
	}
}
LL dp1(int rt, int rt1) {
	dfs1(rt, -1, rt, rt1);
	return F[rt][0];
}
LL dp2(int rt) {
	dfs2(rt);
	return max(F[rt][0], F[rt][1]);
}
LL solve(int rt) {
	h1 = h2 = 0; dfs(rt, -1);
	if (h1 != 0) return max(dp1(h1, h2), dp1(h2, h1));
	else return dp2(rt);
}
int main() {
	int n = getint(), x;
	for (int i = 1; i <= n; ++i) {
		v[i] = getint();
		x = getint();
		ins(x, i);
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			ans += solve(i);
	printf("%lld", ans);
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = ~0ull>>2;
const int maxnode = 2000005;
const int maxedge = maxnode * 8;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
struct edge_type {
    int to, next;
	LL r;
} edge[maxedge];
int S, T, cnte = 1, h[maxnode];
int Q[maxnode];
void ins(int u, int v, LL f) {
    ++cnte;
    edge[cnte].to = v;
    edge[cnte].r = f;
    edge[cnte].next = h[u];
    h[u] = cnte;
    ++cnte;
    edge[cnte].to = u;
    edge[cnte].r = 0;
    edge[cnte].next = h[v];
    h[v] = cnte;
}
int tail, head, d[maxnode], cur[maxnode];
bool bfs() {
    tail = head = 0;
    for (int i = S; i <= T; ++i) d[i] = -1;
    Q[tail++] = S;
    d[S] = 0;
    int now;
    while (head < tail) {
        now = Q[head++];
        for (int i = h[now]; i; i = edge[i].next) {
            if (d[edge[i].to] == -1 && edge[i].r) {
                d[edge[i].to] = d[now] + 1;
                Q[tail++] = edge[i].to;
            }
        }
    }
    return d[T] != -1;
}
LL dfs(int now, LL a) {
    if (T == now || a == 0) return a;
    LL ret = 0, f;
    for (int &i = cur[now]; i; i = edge[i].next) {
        if (d[edge[i].to] != d[now]+1) continue;
        if (f = dfs(edge[i].to, min(a, edge[i].r))) {
            a -= f;
            ret += f;
            edge[i].r -= f;
            edge[i^1].r += f;
            if (a == 0) break;
        }
    }
    if (ret == 0) d[now] = -1;
    return ret;
}
LL Dinic() {
    LL ret = 0;
    while (bfs()) {
        for (int i = S; i <= T; ++i)
            cur[i] = h[i];
        ret += dfs(S, INF);
    }
    return ret;
}
int main() {
	S = 0; T = 2000001;
	int n = getint(), x, y;
	LL sum = 0;
	for (int i = 1; i <= n; ++i) {
		x = getint(); y = getint();
		sum += x;
		ins(S, i, x);
		ins(i+1000000, T, x);
		ins(i, y+1000000, INF);
		ins(y, i+1000000, INF);
	}
	LL ans = Dinic();
	ans >>= 1;
	printf("%lld", sum - ans);
}