この記事は、AOJ-ICPC Advent Calendarの記事です。
余ったところと足りないところの間にDAGのとおりに辺を貼り、最小費用流。
オーダーとしては同じはずの「最小流量制約つきフロー流すだけ」ではTLEするのでなんだか気に入らない。
#include<stdio.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; long long INF=99999999; int in[1100]; int out[1100]; vector<pair<int,int> >g[1100]; int ijk[1100]; int v[1100]; int tp[1100]; int now; void dfs(int a){ v[a]=1; for(int i=0;i<g[a].size();i++){ if(v[g[a][i].first])continue; dfs(g[a][i].first); } tp[now--]=a; } int main(){ int a;scanf("%d",&a); MCF::init(a+2); int sum=0; long long ans=0; for(int i=0;i<a;i++){ int p; scanf("%d",&p); sum+=p; out[i]=p; for(int j=0;j<p;j++){ int s,t;scanf("%d%d",&s,&t); ans+=t; s--; g[i].push_back(make_pair(s,t)); in[s]++; } } int fl=0; now=a-1; for(int i=0;i<a;i++){ if(v[i])continue; dfs(i); } for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ MCF::ae(i,g[i][j].first,INF,g[i][j].second); } } for(int i=0;i<a;i++){ if(i==0||out[i]<in[i]){ if(i==0)MCF::ae(a,i,INF,0); else MCF::ae(a,i,in[i]-out[i],0); } if(out[i]>in[i]){ fl+=out[i]-in[i]; MCF::ae(i,a+1,out[i]-in[i],0); } } MCF::solve(a,a+1,fl); long long ret=MCF::toc+ans; printf("%lld\n",ret); }