C++(clang++ 11.0.1) 解法, 执行用时: 32ms, 内存消耗: 1848K, 提交时间: 2022-12-26 10:05:54

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,S,T,h[N],e[M],ne[M],f[M],w[M];
int incf[N],pre[N],d[N],st[N],idx,q[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    int hh=0,tt=1;
    q[0]=S,d[S]=0,incf[S]=1e9;
    while(hh!=tt){
        int t=q[hh++];
        if(hh==N)hh=0;
        st[t]=0;
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(f[i]&&d[ver]>d[t]+w[i]){
                d[ver]=d[t]+w[i];
                pre[ver]=i;
                incf[ver]=min(incf[t],f[i]);
                if(!st[ver]){
                    st[ver]=1;
                    q[tt++]=ver;
                    if(tt==N)tt=0;
                    
                }
            }
        }
    }
    return incf[T]>0;
}
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=incf[T];
        flow+=t;
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
int A[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    memset(h,-1,sizeof h);
    cin>>n;
    S=0,T=N-1;
    add(T,1,1e9,0);
    int sum=0;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        while(k--){
            int j,w;
            cin>>j>>w;
            add(i,j,1e9,w);
            sum+=w;
            A[i]--,A[j]++;
        }
    }
    for(int i=2;i<=n;i++)add(i,1,1e9,0);
    for(int i=1;i<=n;i++){
        if(A[i]>0)add(S,i,A[i],0);
        if(A[i]<0)add(i,T,-A[i],0);
    }
    
    int flow,cost;
    EK(flow,cost);
//     cout<<flow<<" "<<cost;
    cout<<cost+sum;
}