AC日记——[Sdoi2010]星际竞速 bzoj 1927

1927

思路：

　　连边，拆点；

　　每个点拆成i，i+n，都向t连边；

　　i到t表示高速模式，i+n到t表示跳跃模式；

　　然后读入路径，如果u>v，则交换u，v；

　　u向v+n连边；

　　spfa跑最小费用；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 805

#define maxm 7000000

#define INF 0x7fffffff

int dis[maxn<<],cnt=,s,t,que[maxm],pre[maxn<<],ans;

int n,m,head[maxn<<],E[maxm],V[maxm],F[maxm],W[maxm];

bool if_[maxn<<];

inline void in(int &now)

{

    register int if_z=;now=;

    register char Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

bool spfa()

{

    for(int i=s;i<=t;i++) dis[i]=INF,pre[i]=-,if_[i]=false;

    int h=,tail=;dis[s]=,if_[s]=true,que[]=s;

    while(h<tail)

    {

        int now=que[h++];if_[now]=false;

        for(int i=head[now];i;i=E[i])

        {

            if(F[i]>&&dis[V[i]]>dis[now]+W[i])

            {

                pre[V[i]]=i;

                dis[V[i]]=dis[now]+W[i];

                if(!if_[V[i]])

                {

                    if_[V[i]]=true;

                    que[tail++]=V[i];

                }

            }

        }

    }

    return dis[t]!=INF;

}

int main()

{

    in(n),in(m);

    t=n*+;int u,v,pos;

    for(int i=;i<=n;i++)

    {

        in(pos);

        E[++cnt]=head[s],V[cnt]=i,F[cnt]=,W[cnt]=,head[s]=cnt;

        E[++cnt]=head[i],V[cnt]=s,F[cnt]=,W[cnt]=,head[i]=cnt;

        E[++cnt]=head[s],V[cnt]=i+n,F[cnt]=,W[cnt]=pos,head[s]=cnt;

        E[++cnt]=head[i+n],V[cnt]=s,F[cnt]=,W[cnt]=-pos,head[i+n]=cnt;

        E[++cnt]=head[i+n],V[cnt]=t,F[cnt]=,W[cnt]=,head[i+n]=cnt;

        E[++cnt]=head[t],V[cnt]=i+n,F[cnt]=,W[cnt]=,head[t]=cnt;

    }

    while(m--)

    {

        in(u),in(v),in(pos);

        if(u>v) swap(u,v);

        E[++cnt]=head[u],V[cnt]=v+n,F[cnt]=,W[cnt]=pos,head[u]=cnt;

        E[++cnt]=head[v+n],V[cnt]=u,F[cnt]=,W[cnt]=-pos,head[v+n]=cnt;

    }

    while(spfa())

    {

        int now=t;pos=INF;

        while(pre[now]!=-) pos=min(pos,F[pre[now]]),now=V[pre[now]^];now=t;

        while(pre[now]!=-) F[pre[now]]-=pos,F[pre[now]^]+=pos,now=V[pre[now]^];

        ans+=pos*dis[t];

    }

    cout<<ans;

    return ;

}