(好吧我承认是有点乱)

Q: 你这样乱构造怎么跟原图等价呢 QAQ？

[$tip:$仔细思考这里为啥是对的]

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 10005
#define inf 1023333333
int n, head[N], k, in[N], out[N], x, t, tot, y, ans, que[N + 5], hh, tt, dis[N], pre[N], cap[N];
bool vis[N];
struct edge{
int to, nxt, w, cap;
}e[N << 3];
inline void addedge (int u, int v, int w, int cap)
{
e[tot] = (edge) {v, head[u], w, cap};
++tot;
e[tot] = (edge) {u, head[v], -w, 0};
++tot;
}
inline bool spfa (int s, int t)
{
que[1] = s; vis[s] = 1;
hh = tt = 1;
fo (i, 1, n + 3)
{
dis[i] = inf;
cap[i] = inf;
}
dis[s] = 0;
while (hh != tt + 1)
{
int u = que[hh];
for (int i = head[u]; i != -1; i = e[i].nxt)
{
int v = e[i].to;
if (e[i].cap && dis[u] + e[i].w < dis[v])
{
pre[v] = i;
dis[v] = dis[u] + e[i].w;
cap[v] = std::min(cap[u], e[i].cap);
if (!vis[v])
{
vis[v] = 1;
tt++;
if (tt == N) tt -= N;
que[tt] = v;
}
}
}
vis[u] = 0;
hh++;
if (hh == N) hh -= N;
}
return dis[t] != inf;
}
inline void updata (int s, int t)
{
int i = t;
while (i != s)
{
//      printf("%d <- ", i);
e[pre[i]].cap -= cap[t];
e[pre[i] ^ 1].cap += cap[t];
i = e[pre[i] ^ 1].to;
}
//  printf("%d\n", i);
ans += dis[t] * cap[t];
}
inline void costflow (int s, int t)
{
while (spfa(s, t))
updata(s, t);
}
int main ()
{
//  freopen("miao.txt", "r", stdin);
scanf("%d", &n);
fo (i, 1, n)
{
scanf("%d", &k);
fo (j, 1, k)
{
scanf("%d %d", &x, &t);
++in[x];
ans += t;//可爱的必要弧当然是先加进答案里面啦
}
out[i] = k;
if (1 < i)
addedge(i, n + 1, 0, inf);
}
addedge(n + 1, 1, 0, inf);
y = n + 2, x = n + 3;
fo (i, 1, n)//如果一个点有出度，就由它连向 y，如果一个点有入度，就由 x 连向它
{
if (out[i] < in[i]) addedge(x, i, 0, in[i] - out[i]); else
if (out[i] > in[i]) addedge(i, y, 0, out[i] - in[i]);
}
costflow(x, y);
printf("%d", ans);
return 0;
}