BZOJ-1877: [SDOI2009]晨跑

[文章目录]

Description

给出一张有边权的有向图,询问1~n最多有多少条经过的点互相不重的路径,并且在路径条数最多的情况下,输出最小路程。

将每个点拆点限流,1~n的最大流即为答案,又因为每条路径流量最大为1,所以将长度设为边的费用,所得到的最小费用即为最小路程。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,head[410],to[50000],nxt[50000],f[50000],w[50000],cnt=1;
int ans,cos;
inline void add(int x,int y,int z)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
    f[cnt]=1;
    w[cnt]=z;
    to[++cnt]=x;
    nxt[cnt]=head[y];
    head[y]=cnt;
    f[cnt]=0;
    w[cnt]=-z;
}
int dis[410],path[410];
bool v[410];
queue<int>q;
bool spfa()
{
    memset(dis,0x3f,sizeof dis);
    while(!q.empty()) q.pop();
    memset(v,0,sizeof v);
    dis[s]=0; q.push(s); v[s]=1;
    int x,y;
    while(!q.empty())
    {
        x=q.front(); q.pop(); v[x]=0;
        for(int i=head[x];i;i=nxt[i])
            if(f[i]>0&&dis[y=to[i]]>dis[x]+w[i])
            {
                dis[y]=dis[x]+w[i];
                path[y]=i^1;
                if(!v[y]) q.push(y),v[y]=1;
            }
    }
    return dis[t]<0x3f3f3f3f;
}
void minflow()
{
    while(spfa())
    {
        int tmp=1<<30;
        for(int i=t;i!=s;i=to[path[i]]) tmp=min(tmp,f[path[i]^1]);
        ans+=tmp;
        for(int i=t;i!=s;i=to[path[i]])
        {
            f[path[i]]+=tmp; f[path[i]^1]-=tmp;
            cos+=w[path[i]^1]*tmp;
        } 
    }
}
int main()
{
    scanf("%d%d",&n,&m);s=1+n,t=n;
    for(int i=1;i<=n;i++) add(i,i+n,0);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x+n,y,z);
    }
    minflow();
    printf("%d %d\n",ans,cos);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注