有下界的费用流。
题解传送门（orz跪烂。。。）:http://blog.csdn.net/popoqqq/article/details/43024221
不太好理解，需要细心揣摩=_=
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 305 #define M 5005 using namespace std; const int INF = 1<<30; bool inq[N]; int n, m, cnt=1, S, T, ans=0, last[N], f[N], from[N], cost[N]; struct edge{int next,to,flow,cost;}e[(M+N+M+N)<<1]; void add(int a, int b, int c, int d) { e[++cnt]=(edge){last[a],b,c,d}; last[a]=cnt; } void link(int a, int b, int c, int d) { add(a,b,c,d); add(b,a,0,-d); } int EK() { queue<int> q; memset(cost,63,sizeof(cost)); q.push(S); f[S]=INF;cost[S]=0;from[S]=0;f[T]=0; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(e[i].flow && cost[x]+e[i].cost<cost[y]) { cost[y]=cost[x]+e[i].cost; f[y]=min(f[x],e[i].flow); from[y]=i; if(!inq[y]) { inq[y]=1; q.push(y); } } } } if(!f[T])return false; ans+=f[T]*cost[T]; for(int i = from[T]; i; i=from[e[i^1].to]) { e[i].flow-=f[T]; e[i^1].flow+=f[T]; } return true; } int main() { scanf("%d",&n); S=0;T=n+1; for(int i = 1; i <= n; i++) { scanf("%d",&m); for(int j = 1; j <= m; j++) { int to, v; scanf("%d%d",&to,&v); link(i,to,INF,v); link(S,to,1,v); } link(i,T,m,0); if(i!=1) link(i,1,INF,0); } while(EK()); printf("%d\n",ans); return 0; }