2019杭电多校1005 Path 最短路+最大流（最小割）

现在假设受众已有 求图的所有最短路径 的前置知识

推荐阅读：白书P209 看懂最大流&最小割

今天没时间重构代码了。。。

就随便注释一下

题目呢是签到题

意思是给一个有向图

一个人要从1点走到n点

我们要阻碍他走最短路

而你堵塞一条边的代价就是这条边的长度

问最小代价

要是看懂了最小割
就知道这题几乎就是板子题

先用优先队列优化最短路，求所有最短路径的所有边
题解的方法可以学一手

采用的方法是先更新好所有点的最短距离 （题中的sp数组）
然后遍历所有边
接着如果说两个点的最短距离之差刚好是边的长度
那么这条边就是在最短路上

就是题解那个蜜汁公式的意思

for(int pos=1;pos<=n;++pos)
    for(auto &e : D::G[pos])
        if(sp[e.to]-sp[pos]==e.v)
            I::AddEdge(pos,e.to,e.v);

上图的下面的for等价于

for(int i=0;i<D::G[pos].size();i++){
    D::Edge e=D::G[pos][i];
}

学一手auto自适应类型

然后用最大流求答案。。。。

似乎就没了

#include 

template 
bool Reduce(T &a,T const &b) {
    return a>b?a=b,1:0;
}

const int XN=1e4+11;
const int INF=2e9;
const long long oo=1e18;

int n;
long long sp[XN];

namespace D {
    struct Edge {
        int to,v;
    };

    std::vector G[XN];
    //优先队列优化
    void Run() {
        static bool ud[XN];
        std::priority_queue,std::vector >,std::greater > > Q;//小根堆
        std::fill(sp+1,sp+1+n,oo);
        std::fill(ud+1,ud+1+n,0);
        sp[1]=0;
        Q.push(std::make_pair(0,1));
        while(!Q.empty()) {
            int pos=Q.top().second;Q.pop();
            if(ud[pos])
                continue;
            ud[pos]=1;
            for(auto int & e : G[pos]) {
                int u=e.to;
                if(Reduce(sp[u],sp[pos]+e.v))
                    Q.push(std::make_pair(sp[u],u));
            }
        }
    }
}

namespace I {
    //最大流求解
    struct Edge {
        int to,cap,v;
        Edge *rev,*pre;
    }*G[XN],*preArc[XN];

    void AddEdge(int x,int y,int c) {
        G[x]=new Edge{y,c,0,NULL,G[x]};
        G[y]=new Edge{x,0,0,G[x],G[y]};
        G[x]->rev=G[y];
    }

    int Aug() {
        int d=INF;
        for(int pos=n;preArc[pos];pos=preArc[pos]->rev->to)
            Reduce(d,preArc[pos]->cap-preArc[pos]->v);
        for(int pos=n;preArc[pos];pos=preArc[pos]->rev->to) {
            preArc[pos]->v+=d;
            preArc[pos]->rev->v-=d;
        }
        return d;
    }

    long long Run() {
        static int num[XN],d[XN];
        static Edge *cArc[XN];
        std::fill(num+1,num+n,0);
        std::fill(d+1,d+1+n,0);
        std::copy(G+1,G+1+n,cArc+1);
        num[0]=n;preArc[1]=0;
        long long flow=0;
        for(int pos=1;d[1]<n;) {
            if(pos==n) {
                flow+=Aug();
                pos=1;
            }
            bool adv=0;
            for(Edge *&e=cArc[pos];e;e=e->pre) {
                int u=e->to;
                if(e->cap>e->v && d[u]+1==d[pos]) {
                    adv=1;
                    preArc[pos=u]=e;
                    break;
                }
            }
            if(!adv) {
                if(--num[d[pos]]==0)
                    break;
                d[pos]=n;
                for(Edge *e=cArc[pos]=G[pos];e;e=e->pre)
                    if(e->cap>e->v)
                        Reduce(d[pos],d[e->to]+1);
                num[d[pos]]++;
                if(pos!=1)
                    pos=preArc[pos]->rev->to;//cArc
            }
        }
        return flow;
    }
}

int main() {
    //freopen("test1.in","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int m;std::cin>>n>>m;
        for(int i=1;i<=n;++i) {
            D::G[i].clear();
            I::G[i]=0;
        }
        for(int i=1;i<=m;++i) {
            int x,y,v;
            std::cin>>x>>y>>v;
            D::G[x].push_back({y,v});
        }

        D::Run();

        if(sp[n]==oo)
            std::cout<<0<<'\n';
        else {
            //蜜汁公式 求出所有最短路径边
            for(int pos=1;pos<=n;++pos)
                for(auto &e : D::G[pos])
                    if(sp[e.to]-sp[pos]==e.v)
                        I::AddEdge(pos,e.to,e.v);

            std::cout<<I::Run()<<'\n';
        }
    }
    return 0;
}