[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)

发布于 2018-03-25  94 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)

Description

皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。
火箭队一共有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一开始K个人都在0号点。
由于火箭队的重重布防,要想摧毁K号据点,必须按照顺序先摧毁1到K-1号据点,并且,如果K-1号据点没有被摧毁,由于防御的连锁性,小智一行任何一个人进入据点K,都会被发现,并产生严重后果。因此,在K-1号据点被摧毁之前,任何人是不能够经过K号据点的。
为了简化问题,我们忽略战斗环节,小智一行任何一个人经过K号据点即认为K号据点被摧毁。被摧毁的据点依然是可以被经过的。
K个人是可以分头行动的,只要有任何一个人在K-1号据点被摧毁之后,经过K号据点,K号据点就被摧毁了。显然的,只要N号据点被摧毁,皮卡丘就得救了。
野外的道路是不安全的,因此小智一行希望在摧毁N号据点救出皮卡丘的同时,使得K个人所经过的道路的长度总和最少。
请你帮助小智设计一个最佳的营救方案吧!

Tag

网络流,二分图

解决思路

如果是DAG,那么问题就是求一个费用最小的用K条不相交,可以用拆点的方式解决。但是这里是可能有环的无向图,并且还要求必须先经过标号小的点才能经过标号大的点。
从标号小的走到标号大的?这似乎构成了DAG。我们先考虑一个人怎么走,他一定是依次沿着最短路从小标号走到大标号,并且从u->u+1时不会经过大于u+1的点。这个可以用Floyed最短路预处理出来。
至于多个人的话,其实与一个人是一样的,每一个人都只能向标号更大的地方走。(当然,中间可能经过标号小的,但每一阶段结束的时候一定是走到标号更大的)
所以我们把原图转化为一个只从标号小的走到标号大的的DAG,然后考虑在这个DAG上求覆盖所有点的最短的K条链。
对于每一个点拆成两个点分别叫做入点和出点,记作u和u',从u到汇点连容量为1,费用为0的边,表示需要到达这个点;再从源点向u'连容量为1费用为0的边。第二条边可以看作是补充第一条边流走的流量的,你可以认为两条边是流量流入汇点再从源点流出,由于原图是连通的一定存在解,所以这样是对的。
再对于新DAG中的一条从小标号走到大标号的边u->v,连边u'->v,容量无穷,费用为其距离。
最后由于有K个人,所以从源点向0号点的出点连一条容量为K费用为0的边,你可以当做0的入点没有用。
然后在这个图上求最小费用最大流就可以得到最优解了。
为了方便处理,在代码中,我把每一个但点的标号都加了一,这样就不需要考虑0了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=160*2;
const int maxM=maxN*maxN*10;
const int inf=2147483647;

int n,m,K;

namespace Flow//最小费用最大流
{
    class Edge
    {
    public:
        int u,v,flow,w;
    };

    int S,T;
    int edgecnt=-1,Head[maxN],Next[maxM];
    Edge E[maxM];
    int Dist[maxN],Flow[maxN],Path[maxN];
    queue<int> Queue;
    bool inqueue[maxN];

    void Add(int u,int v,int flow,int w)
    {
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;
        E[edgecnt].u=u;E[edgecnt].v=v;E[edgecnt].w=w;E[edgecnt].flow=flow;
        return;
    }

    void Add_Edge(int u,int v,int flow,int w)
    {
        Add(u,v,flow,w);Add(v,u,0,-w);
        return;
    }

    bool Spfa()
    {
        mem(Dist,-1);
        Dist[S]=0;Flow[S]=inf;inqueue[S]=1;
        while (!Queue.empty()) Queue.pop();
        Queue.push(S);
        do
        {
            int u=Queue.front();Queue.pop();
            for (int i=Head[u];i!=-1;i=Next[i])
            {
                if ((E[i].flow>0)&&((Dist[E[i].v]==-1)||(Dist[E[i].v]>Dist[u]+E[i].w)))
                {
                    Dist[E[i].v]=Dist[u]+E[i].w;Path[E[i].v]=i;Flow[E[i].v]=min(Flow[u],E[i].flow);
                    if (inqueue[E[i].v]==0){
                        inqueue[E[i].v]=1;Queue.push(E[i].v);
                    }
                }
            }
            inqueue[u]=0;
        }
        while (!Queue.empty());
        if (Dist[T]==-1) return 0;
        return 1;
    }

    int MaxFlow()
    {
        int Ret=0;
        while (Spfa())
        {
            Ret+=Flow[T]*Dist[T];
            int now=T;
            while (now!=S)
            {
                E[Path[now]].flow-=Flow[T];
                E[Path[now]^1].flow+=Flow[T];
                now=E[Path[now]].u;
            }
        }
        return Ret;
    }
}

namespace Floyed//最短路
{
    int Dist[maxN][maxN];
    void Add_Edge(int u,int v,int w)
    {
        if ((Dist[u][v]==-1)||(Dist[u][v]>w)) Dist[u][v]=Dist[v][u]=w;
        return;
    }
    void Floyed()//Floyed最短路
    {
        for (int k=1;k<=n;k++)
        {
            for (int i=1;i<=n;i++)
                if ((i!=k)&&(Dist[i][k]!=-1))
                    for (int j=1;j<=n;j++)
                        if ((i!=j)&&(k!=j)&&(Dist[k][j]!=-1))
                            if ((Dist[i][j]==-1)||(Dist[i][j]>Dist[i][k]+Dist[k][j]))
                                Dist[i][j]=Dist[j][i]=Dist[i][k]+Dist[k][j];
            for (int i=1;i<k;i++) if (Dist[i][k]!=-1) Flow::Add_Edge(i+n,k,inf,Dist[i][k]);//由于有不能经过标号大于i的点的限制,所以在这里就要把边加到新图去。,
        }
        return;
    }
}

int main()
{
    mem(Floyed::Dist,-1);mem(Flow::Head,-1);
    scanf("%d%d%d",&n,&m,&K);n++;
    for (int i=1;i<=m;i++)//原图连边
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);u++;v++;
        Floyed::Add_Edge(u,v,w);
    }
    Floyed::Floyed();//Floyed求有限制的最短路,同时在新的DAG中连边
    Flow::S=n*2+1;Flow::T=Flow::S+1;
    for (int i=2;i<=n;i++) Flow::Add_Edge(i,Flow::T,1,0),Flow::Add_Edge(Flow::S,i+n,1,0);//添加与源汇点的边
    Flow::Add_Edge(Flow::S,n+1,K,0);//添加源点与起点的边
    printf("%d\n",Flow::MaxFlow());//最小费用最大流
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2324][ZJOI2011]营救皮卡丘(网络流,最短路)


HNCJ OIer