题意：给定DAG，通过每条边需要时间。
从某号点回到1号点不需要时间。
从1号点出发，求最少要多久才能走完所有边。
解：
有源汇有上下界最小费用可行流。
直接连边，费用为时间，下界为1，无上界。
每个点都可能是终点，往t连边。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring> const int N = , M = , INF = 0x3f3f3f3f; struct Edge {
int nex, v, c, len;
}edge[M << ]; int top = ; int e[N], d[N], vis[N], pre[N], flow[N], ot[N];
std::queue<int> Q; inline void add(int x, int y, int z, int w) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].len = w;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].len = -w;
edge[top].nex = e[y];
e[y] = top;
return;
} inline bool SPFA(int s, int t) {
memset(d, 0x3f, sizeof(d));
d[s] = ;
flow[s] = INF;
vis[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
vis[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(edge[i].c && d[y] > d[x] + edge[i].len) {
d[y] = d[x] + edge[i].len;
pre[y] = i;
flow[y] = std::min(flow[x], edge[i].c);
if(!vis[y]) {
vis[y] = ;
Q.push(y);
}
}
}
}
return d[t] < INF;
} inline void update(int s, int t) {
int temp = flow[t];
while(t != s) {
int i = pre[t];
edge[i].c -= temp;
edge[i ^ ].c += temp;
t = edge[i ^ ].v;
}
return;
} inline int solve(int s, int t, int &cost) {
int ans = ;
cost = ;
while(SPFA(s, t)) {
ans += flow[t];
cost += flow[t] * d[t];
update(s, t);
}
return ans;
} int main() {
int n, cost = ;
scanf("%d", &n);
int ss = n + , tt = n + , t = n + ;
for(int i = , x, y, z; i <= n; i++) {
scanf("%d", &x);
for(int j = ; j <= x; j++) {
scanf("%d%d", &y, &z);
// i -> y z
add(i, y, INF, z);
ot[i]++;
ot[y]--;
cost += z;
}
add(i, t, INF, );
}
for(int i = ; i <= n; i++) {
if(ot[i] > ) {
add(i, tt, ot[i], );
}
else {
add(ss, i, -ot[i], );
}
}
add(t, , INF, );
int ans;
solve(ss, tt, ans);
printf("%d", ans + cost);
return ;
}
AC代码