poj 2391 floyed + 2 분 매 거 + 최대 흐름

전송 문
제목: n 개의 외양간 에 소 가 몇 개 있 고 자신의 용량 이 있 습 니 다. 비가 오 면 소 는 비 를 피해 야 합 니 다. 외양간 사 이 를 걷 는 데 시간 이 필요 합 니 다. 모든 소 에 게 비 를 피 하 는 최소 시간 을 물 어보 세 요.
사고: 먼저 flyd 번, 두 외양간 의 최소 시간 을 얻 은 다음 에 2 분 의 매 거 시간 을 들 어 최대 흐름 에 이 르 렀 는 지 아 닌 지 를 보 는 것 이 이렇게 간단 하 다.
소감: 이 문 제 는 시간 이 좀 걸 려 요. 제 가 오래 버 텼 던 EK 알고리즘 이 드디어 여기 서 무릎 을 꿇 었 고 도저히 일어나 지 못 하 는 상황 이에 요...그래서 오늘 아침부터 dinic 을 보고 마음대로 보 았 습 니 다. A 문제 가 마음 에 들 어서 바로 모델 에 따라 각색 하여 두 드 렸 습 니 다. 그 후에 wa 는 롱 롱 롱 범위 인지 wa 인지 알 게 되 었 습 니 다. 나중에 야 한 곳 의 가치 가 잘못 되 었 다 는 것 을 알 게 되 었 습 니 다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1<<30
using namespace std;
long long int mm=100000000000000ll;
int m,n,cow[510],con[510],csum,consum;
int fst[510],next[200000],node[200000],c[200000];
int f[200000],en,pre[520],lu[510],dis[510];
int low[520];
long long int l[200000],a[510][510];
bool block[510];
void init()
{
    int u,v;
    long long int len;
    csum=0;
    consum=0;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&cow[i],&con[i]);
        csum+=cow[i];
        consum+=con[i];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            a[i][j]=mm;
        }
        a[i][i]=0;
    }
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%lld",&u,&v,&len);
        if(a[u][v]>len)
        {
            a[u][v]=a[v][u]=len;
        }
    }
    for(int x=1; x<=n; x++)
    {
        for(int y=1; y<=n; y++)
        {
            for(int z=1; z<=n; z++)
            {
                if(a[y][z]>a[y][x]+a[x][z])
                {
                    a[y][z]=a[y][x]+a[x][z];
                }
            }
        }
    }
}
void add(int u,int v,int cc,long long int la)
{
    next[en]=fst[u];
    fst[u]=en;
    node[en]=v;
    c[en]=cc;
    l[en]=la;
    en++;
}
void build(long long int la)
{
    memset(fst,-1,sizeof(fst));
    en=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(a[i][j]>la)continue;
            add(i,j+n,maxn,a[i][j]);
            add(j+n,i,0,a[i][j]);
        }
        add(0,i,cow[i],0);
        add(i,0,0,0);
        add(i+n,2*n+1,con[i],0);
        add(2*n+1,i+n,0,0);
    }
}
void lays(int s,int t)
{
    int q[3000],front=0,end=0;
    for(int i=s; i<=t; i++)dis[i]=maxn;
    q[end++]=s;
    dis[s]=0;
    while(front<end)
    {
        int u=q[front++];
        for(int i=fst[u]; i!=-1; i=next[i])
        {
            int v=node[i];
            if(dis[v]==maxn&&c[i]>f[i])
            {
                dis[v]=dis[u]+1;
                q[end++]=v;
            }
        }
    }
}
int dinic(int s,int t)
{
    int flow=0;
    memset(f,0,sizeof(f));
    memset(block,0,sizeof(block));
    memset(low,0,sizeof(low));
    lays(s,t);
    int top=s;
    while(dis[t]!=maxn)
    {
        bool flag=false;
        low[s]=maxn;
        int i,v;
        for(i=fst[top]; i!=-1; i=next[i])
        {
            v=node[i];
            if(c[i]>f[i]&&dis[v]==dis[top]+1&&!block[v])
            {
                flag=true;
                break;
            }
        }
        if(flag)
        {
            low[v]=c[i]-f[i];
            if(low[v]>low[top])low[v]=low[top];
            pre[v]=top;
            top=v;
            lu[v]=i;
            if(top==t)
            {
                flow+=low[t];
                int j=top;
                while(j!=s)
                {
                    int k=lu[j];
                    f[k]+=low[t];
                    f[k^1]-=low[t];
                    j=pre[j];
                }
                top=s;
                memset(low,0,sizeof(low));
            }
        }
        else
        {
            block[top]=1;
            if(top!=s)top=pre[top];
        }
        if(block[s])
        {
            lays(s,t);
            memset(block,0,sizeof(block));
        }
    }
    return flow;
}
void solve()
{
    long long int ans=mm;
    long long int high=mm,low=0,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        build(mid);
        int aaa=dinic(0,2*n+1);
        if(aaa==csum)
        {
            ans=mid;
            high=mid-1;
        }
        else low=mid+1;
    }
    if(ans==mm)cout<<-1<<endl;
    else cout<<ans<<endl;
}
int main()
{
    init();
    if(csum>consum)
    {
        cout<<-1<<endl;
        return 0;
    }
    solve();
    return 0;
}