【解题报告】[ZJOI2011]营救皮卡丘

题目链接

---

首先 , 我们可以轻易的从数据范围N<<M看出，这是一道网络流

在得出算法后，我们开始考虑建模。

根据题目条件：

1. 在经过K-1号点之前，任何人是不能够经过K号据点的。，同时由于 $N\le150$ 这里很容易想到跑一遍带限制的Floyd，即由 $x\to y$ ，不经过节点编号比 $y$ 大的点，再从所有编号小的点向编号大的点连一条流量为 $1$ , 边权为 $dis(i,j)$ 的边.
2. 同时，我们最终要到达 $N$ 号点，即每个点均需到达至少一次。所以我们将除了 $0$ 号点以外的点都向汇点连一条流量为 $1$ ，边权为 $0$ 的边
3. 小智一行K人从真新镇出发.这个很好解决，我们直接从源点向 $0$ 号点连一条流量为 $K$,边权为 $0$ 的边

在粗略建模完成后，我们发现了一个问题: 从源点出去的流量远小于我们需要的最大流，所以我们考虑网络流常用的拆点思路解决。

我们将每个点拆为入点和出点，将每个点的入点向汇点连边，再将源点向每个点的出点连一条流量为 $1$ 边权为 $0$ 的边，其余点之间的连边即从 $x$ 的出点，向 $y$ 的入点连边即可

$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$

//核心建模代码
    for(register int u,v,w,i=1;i<=m;++i)
    {
        u=read(),v=read(),w=read();
        ++u,++v;
        f[u][v]=f[v][u]=min(f[u][v],w);
    }
    for(register int i=1;i<=n;++i)f[i][i]=0;
    for(register int k=1;k<=n;++k)
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=n;++j)
                if(k<i||k<j)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(register int i=1;i<=n;++i)
        for(register int j=i+1;j<=n;++j)
            if(f[i][j]!=inf)addedge(i,j+n,inf,f[i][j]);
    addedge(s,1,lim,0);
    for(register int i=1;i<=n;++i)
    {
        addedge(i+n,t,1,0);
        if(i!=1)addedge(s,i,1,0);
    }