M_sea

洛谷3171 [CQOI2015]网络吞吐量
LuoguBZOJ分析简化题意:给出一个无向图,第 $i$ 个点只能用 $c[i]$ 次,求能构成多少条最短路。首...
扫描右侧二维码阅读全文
17
2019/03

洛谷3171 [CQOI2015]网络吞吐量

Luogu

BZOJ

分析

简化题意:给出一个无向图,第 $i$ 个点只能用 $c[i]$ 次,求能构成多少条最短路。


首先把会出现在最短路上的边拿出来。

跑一遍 $\mathrm{dijkstra}$ ,然后如果 $dis[u]+w=dis[v]$ ,那么 $(u,v)$ 就会出现在最短路上。

然后,考虑网络流。

因为题目中是对点的限制,于是拆点。

  • 入点 $s_i$ 向出点 $t_i$ 连边,如果 $i=1$ 或 $i=n$ ,容量为 $\infty$ ,否则容量为 $c[i]$ 。
  • 源点往 $s_1$ 连 $\infty$ 边, $t_n$ 往汇点连 $\infty$ 边。
  • 如果 $(u,v)$ 会出现在最短路上,那么 $t_u$ 往 $s_v$ 连容量为 $\infty$ 的边。

最大流就是答案。注意要开 $\mathrm{long\ long}$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;
const int M=100000+10;
const ll inf=1e18;

int n,m;

namespace NF {
    int s,t;
    struct Edge { int v; ll w; int nxt; } e[1000010];
    int head[100010],lv[100010];

    inline void addEdge(int u,int v,ll w) {
        static int cnt=2;
        e[cnt]=(Edge){v,w,head[u]},head[u]=cnt++;
        e[cnt]=(Edge){u,0,head[v]},head[v]=cnt++;
    }
    
    inline int bfs() {
        fill(lv+s,lv+t+1,0),lv[s]=1;
        queue<int> Q; Q.push(s);
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v,w=e[i].w;
                if (w&&!lv[v]) lv[v]=lv[u]+1,Q.push(v);
            }
        }
        return lv[t]!=0;
    }
    
    inline ll dfs(int u,ll cpflow) {
        if (u==t||!cpflow) return cpflow;
        ll addflow=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&lv[v]==lv[u]+1) {
                ll tmpadd=dfs(v,min(cpflow,e[i].w));
                e[i].w-=tmpadd,e[i^1].w+=tmpadd;
                addflow+=tmpadd,cpflow-=tmpadd;
            }
        }
        if (!addflow) lv[u]=0;
        return addflow;
    }

    inline ll dinic() {
        ll res=0;
        while (bfs()) res+=dfs(s,inf);
        return res;
    }
}

namespace SSSP {
    struct Edge { int v; ll w; int nxt; } e[M<<1];
    int head[N];

    inline void addEdge(int u,int v,ll w) {
        static int cnt=0;
        e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
    }

    struct node { int u; ll d; };
    bool operator <(node a,node b) { return a.d>b.d; }
    ll dis[N];
    
    inline void dijkstra() {
        fill(dis+1,dis+n+1,inf),dis[1]=0;
        priority_queue<node> Q; Q.push((node){1,0});
        while (!Q.empty()) {
            int u=Q.top().u,d=Q.top().d; Q.pop();
            if (d!=dis[u]) continue;
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v,w=e[i].w;
                if (d+w<dis[v]) dis[v]=d+w,Q.push((node){v,dis[v]});
            }
        }
    }

    inline void work() {
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),addEdge(v,u,w);
        }
        dijkstra();
    }
}

namespace Build {
    int c[N];
    
    inline void work() {
        NF::s=0,NF::t=2*n+1;
        NF::addEdge(NF::s,1,inf),NF::addEdge(2*n,NF::t,inf);
        for (re int i=1;i<=n;++i) {
            c[i]=read();
            if (i!=1&&i!=n) NF::addEdge(i,i+n,c[i]);
            else NF::addEdge(i,i+n,inf);
        }
        for (re int u=1;u<=n;++u)
            for (re int i=SSSP::head[u];i;i=SSSP::e[i].nxt) {
                int v=SSSP::e[i].v,w=SSSP::e[i].w;
                if (SSSP::dis[u]+w==SSSP::dis[v]) NF::addEdge(u+n,v,inf);
            }
    }
}

inline void solve() {
    n=read(),m=read();
    SSSP::work(),Build::work();
    printf("%lld\n",NF::dinic());
}

int main() {
    solve(); return 0;
}
最后修改:2019 年 03 月 17 日 05 : 47 PM

发表评论