AOJ 2627: Multi Path Story

この記事は、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);
}