【题解】Luogu P2153 [SDOI2009]晨跑

原题传送门

一眼应该就能看出是费用流

因为每个交叉路口只能通过一次，所以我们进行拆点，连一条流量为1费用为0的边

再按照题目给的边（是单向边）建图

跑一下MCMF就行了

拆点很套路的~

#include <bits/stdc++.h>

#define N 205

#define M 20005

#define inf (1<<30)

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Min(register int a,register int b)

{

    return a<b?a:b;

}

struct node{

    int to,next,v,c;

}e[(M<<2)+(N<<1)];

int head[N<<1],cnt=1;

inline void add(register int u,register int v,register int val,register int cost)

{

    e[++cnt]=(node){v,head[u],val,cost};

    head[u]=cnt;

}

int n,m,s,t,maxflow=0,mincost=0;

int vis[N<<1],dist[N<<1];

inline bool spfa()

{

    memset(vis,0,sizeof(vis));

    memset(dist,0x3f,sizeof(dist));

    dist[s]=0;

    vis[s]=1;

    queue<int> q;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=0;

        for(register int i=head[u];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dist[v]>dist[u]+e[i].c&&e[i].v)

            {

                dist[v]=dist[u]+e[i].c;

                if(vis[v]==0)

                {

                    q.push(v);

                    vis[v]=1;

                }

            }

        }

    }

    return dist[t]!=0x3f3f3f3f;

}

inline int dfs(register int u,register int flow)

{

    if(u==t)

    {

        vis[t]=1;

        maxflow+=flow;

        return flow;

    }

    int used=0;

    vis[u]=1;

    for(register int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if((vis[v]==0||v==t)&&e[i].v&&dist[v]==dist[u]+e[i].c)

        {

            int tmp=dfs(v,Min(e[i].v,flow-used));

            if(tmp)

            {

                mincost+=e[i].c*tmp;

                used+=tmp;

                e[i].v-=tmp;

                e[i^1].v+=tmp;

            }

            if(used==flow)

                return used;

        }

    }

    return used;

}

inline void MCMF()

{

    while(spfa())

    {

        vis[t]=1;

        while(vis[t])

        {

            memset(vis,0,sizeof(vis));

            dfs(s,inf);

        }

    }

}

int main()

{

    n=read(),m=read();

    s=1,t=n;

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

        add(i,i+n,1,0),add(i+n,i,0,0);

    for(register int i=1;i<=m;++i)

    {

        int u=read(),v=read(),cost=read();

        if(u==1)

            add(u,v,1,cost),add(v,u,0,-cost);

        else if(v==n)

            add(u+n,v,1,cost),add(v,u+n,0,-cost);

        else

            add(u+n,v,1,cost),add(v,u+n,0,-cost);

    }

    MCMF();

    write(maxflow),putchar(' '),write(mincost);

    return 0;

}

巴特西

【题解】Luogu P2153 [SDOI2009]晨跑

原题传送门

一眼应该就能看出是费用流

因为每个交叉路口只能通过一次，所以我们进行拆点，连一条流量为1费用为0的边

再按照题目给的边（是单向边）建图

跑一下MCMF就行了

拆点很套路的~

最新文章

热门文章