[SDOI2009]晨跑

 不得不说感觉SDOI的题都好值得回味啊

思路题:

我们应该如何规避掉重复路线

我们可以将一个点拆成两个点,一个入一个出,这样的话在十字路口就可以防止重复了

容量为一,权值为零,然后变为最小费用最大流

 

之后就比较裸的code了

 

#include<bits/stdc++.h>

using namespace std;
const int N=4e2+7;
const int M=1e5+7;

int n,m;
int head[M>>1],nxt[M],to[M],cost[M],cap[M];

int _=1;
void add(int x,int y,int c,int z)
{
    _++;
    to[_]=y;
    cap[_]=c;
    cost[_]=z;
    nxt[_]=head[x];
    head[x]=_;
    return ;
}
int flow[N],pre[N],xb[N],dis[N],f[N];
int mflow,mcost;

void build(int fa,int ds,int co)
{
    if(fa==1)
    {
        add(1,ds,1,co);
        add(ds,1,0,-co);
        return ;
    }
    if(ds==n)
    {
        add(fa+n,n,1,co);
        add(n,fa+n,0,-co);
        return ;
    }
    
    add(fa+n,ds,1,co);
    add(ds,fa+n,0,-co);
    return ;
}
queue<int >q;

bool bfs(int s,int t)
{
    memset(dis,127,sizeof(dis));
    memset(f,0,sizeof(f));
    int maxx=dis[0];
    while(!q.empty())
    q.pop();
    fill(pre+1,pre+1+n,-1);
    
    f[s]=1;
    dis[s]=0;
    pre[s]=0;
    flow[s]=0x7fffffff;
    q.push(s);
    
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        f[x]=0;
        
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(cap[i]>0&&dis[y]>dis[x]+cost[i])
            {
                dis[y]=dis[x]+cost[i];
                pre[y]=x;
                xb[y]=i;
                flow[y]=min(flow[x],cap[i]);
                if(!f[y])
                {
                    f[y]=1;
                    q.push(y);
                }
            }
            
        }
    }
    if(dis[t]>=maxx)
    return 0;
    else
    return 1;
}

void makeflow(int x,int y)
{
    while(bfs(x,y))
    {
        int e=y;
        while(e!=x)
        {
             cap[xb[e]]-=flow[y];
             cap[xb[e]^1]+=flow[y];
             e=pre[e];            

        }
        mflow+=flow[y];
        mcost+=flow[y]*dis[y];
    }
    
    return ;
}



int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    
    for(int i=2;i<n;i++)
    {
        add(i,i+n,1,0);
        add(i+n,i,0,0);
    }
    
    for(int i=1;i<=m;i++)
    {
        int p,w,e;
        cin>>p>>w>>e;
        build(p,w,e);
    }
    makeflow(1,n);
    
    cout<<mflow<<" "<<mcost;
    
    return 0;
}

 

[SDOI2009]晨跑

上一篇:RK3568 Sensor FAQ


下一篇:RabbitMQ消息队列