洛谷 P3171 [CQOI2015]网络吞吐量 题解【网络流】【最短路计数】

作者: wjyyy 分类: 最短路,最短路计数,网络流,解题报告 发布时间: 2018-07-07 17:04

点击量：128

 

   我自己AC的做法居然是错的。。。

 

题目描述

路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。

输入输出格式

输入格式：

输入文件第一行包含两个空格分开的正整数n和m，分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行，每行包含三个空格分开的正整数a、b和d，表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行，每行包含一个正整数c，分别给出每一个路由器的吞吐量。

输出格式：

输出一个整数，为题目所求吞吐量。

输入输出样例

输入样例#1：
7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1
输出样例#1：
70

说明

对于100%的数据，n<=500，m<=100000，d,c<=10^9

 

   首先，这个题一定要开long long，不然会和没写一样。。。

 

非完美解法：

   看到这个题，用网络流来限流当然是第一想法。于是先spfa求最短路，接着枚举每个点是否在最短路上。判断方法：从起点/终点出发各跑一遍最短路，记录dis[0]和dis[1]，最后枚举每条边是否满足$ dis[0][u]+w+dis[1][v]=dis[0][t]$（t表示终点）。如果在，就把它加入网络流图中，流量为两端点中吞吐量较小的一个。这种做法看上去没有问题，因为两个点相连新吞吐量依赖于较低的点的吞吐量。

 

   不过一个点不一定只有这一条流连接，当有多条流流入且有多条流流出时，它的流量可以被扩充超过它的吞吐量。比如说十字路口这种图：

所有点的吞吐量均为1。

   即使4号点的吞吐量为1，也只能构建出这样的图，而这时最大流为2，不符合题意。当这个十字路口变为度为2k的点时，它的流量可以达到吞吐量×k。

 

   可能是数据不够强，致使我这种非完美解法能通过。

 

正确解法：

   把一个点拆成两个，一个管进入，一个管流出，两个点之间以吞吐量为流量的边连接起来。再把最短路上满足条件的点（分拆点的进出）相连，权值为inf。直接跑1到n的最大流，最大流就是答案了。

非完美Code：

#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
int min(int x,int y)
{
    return x<y?x:y;
}
namespace graph//建了两个图所以用命名空间
{
struct edge
{
    int n;
    int v;
    int nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[501],cnt=-1;
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,v,head[to]);
    head[to]=cnt;
}
void init()
{
    memset(head,-1,sizeof(head));
}
long long dis[2][510];
void spfa(int x)
{
    deque<int> q;
    bool used[510];
    memset(used,0,sizeof(used));
    memset(dis[x!=1],0x3f,sizeof(dis[x!=1]));
    used[x]=1;
    dis[x!=1][x]=0;
    int flag=(x!=1);
    q.push_back(x);
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        for(int i=head[k];~i;i=e[i].nxt)
        {
            if(dis[flag][e[i].n]>dis[flag][k]+e[i].v)
            {
                dis[flag][e[i].n]=dis[flag][k]+e[i].v;
                if(!used[e[i].n])
                {
                    if(q.empty()||dis[flag][e[i].n]<dis[flag][q.front()])
                        q.push_front(e[i].n);
                    else
                        q.push_back(e[i].n);
                    used[e[i].n]=true;
                }
            }
        }
    }
}
}
int flow[510];
long long sum=0;//要开long long
namespace Flow
{
struct edge
{
    int n,v;
    int nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[505],cnt=-1;
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,0,head[to]);
    head[to]=cnt;
}
void init()
{
    memset(head,-1,sizeof(head));
}
int d[505],gap[505];
void bfs(int x)
{
    memset(d,0,sizeof(d));
    int q[505],l=0,r=0;
    q[++r]=x;
    d[x]=1;
    gap[0]=123456;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
        {
            if(!d[e[i].n])
            {
                d[e[i].n]=d[k]+1;
                gap[d[e[i].n]]++;
                q[++r]=e[i].n;
            }
        }
    }
}
void isap(int x)
{
    bfs(x);
    int s=1;
    int pre[505];
    memset(pre,-1,sizeof(pre));
    int cur[505];
    for(int i=1;i<=x;i++)
        cur[i]=head[i];
    while(d[1]<=x)
    {
        if(s==x)
        {
            int minn=1234567890;
            int p=pre[s];
            while(~p)
            {
                minn=min(minn,e[p].v);
                p=pre[e[p^1].n];
            }
            sum+=minn;
            p=pre[s];
            while(~p)
            {
                e[p].v-=minn;
                e[p^1].v+=minn;
                p=pre[e[p^1].n];
            }
            s=1;
        }
        int flag=0;
        for(int i=cur[s];~i;i=e[i].nxt)
            if(e[i].v&&d[e[i].n]+1==d[s])
            {
                pre[e[i].n]=i;
                cur[s]=e[i].nxt;
                flag=1;
                s=e[i].n;
                break;
            }
        if(flag==0)
        {
            int tmp=d[s];
            d[s]=123456789;
            for(int i=head[s];~i;i=e[i].nxt)
                if(e[i].v)
                    d[s]=min(d[s],d[e[i].n]+1);
            gap[tmp]--;
            gap[d[s]]++;
            if(gap[tmp]==0)
                return;
            cur[s]=head[s];
            if(s!=1)
                s=e[pre[s]^1].n;
        }
    }
}
}
int main()
{
    using namespace graph;
    init();
    Flow::init();
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&flow[i]);
    flow[1]=1234567890;
    flow[n]=1234567890;
    spfa(1);
    spfa(n);
    for(int i=1;i<=n;i++)
        for(int j=head[i];~j;j=e[j].nxt)
            if(dis[0][i]+e[j].v+dis[1][e[j].n]==dis[0][n])
                Flow::add(i,e[j].n,min(flow[i],flow[e[j].n]));
    Flow::isap(n);
    printf("%lld\n",sum);
    return 0;
}

 

正解Code：

#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
int min(int x,int y)
{
    return x<y?x:y;
}
long long min(long long x,long long y)
{
    return x<y?x:y;
}
namespace graph
{
struct edge
{
    int n;
    int v;
    int nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[501],cnt=-1;
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,v,head[to]);
    head[to]=cnt;
}
void init()
{
    memset(head,-1,sizeof(head));
}
long long dis[2][510];
void spfa(int x)
{
    deque<int> q;
    bool used[510];
    memset(used,0,sizeof(used));
    memset(dis[x!=1],0x3f,sizeof(dis[x!=1]));
    used[x]=1;
    dis[x!=1][x]=0;
    int flag=(x!=1);
    q.push_back(x);
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        for(int i=head[k];~i;i=e[i].nxt)
        {
            if(dis[flag][e[i].n]>dis[flag][k]+e[i].v)
            {
                dis[flag][e[i].n]=dis[flag][k]+e[i].v;
                if(!used[e[i].n])
                {
                    if(q.empty()||dis[flag][e[i].n]<dis[flag][q.front()])
                        q.push_front(e[i].n);
                    else
                        q.push_back(e[i].n);
                    used[e[i].n]=true;
                }
            }
        }
    }
}
}
long long flow[510];
long long sum=0;
namespace Flow
{
struct edge
{
    int n;
    long long v;
    int nxt;
    edge(int n,long long v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[410000];
int head[1005],cnt=-1;
void add(int from,int to,long long v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,0,head[to]);
    head[to]=cnt;
}
void init()
{
    memset(head,-1,sizeof(head));
}
int d[1005],gap[1005];
void bfs(int x)
{
    memset(d,0,sizeof(d));
    int q[1005],l=0,r=0;
    q[++r]=x;
    d[x]=1;
    gap[0]=123456;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
        {
            if(!d[e[i].n])
            {
                d[e[i].n]=d[k]+1;
                gap[d[e[i].n]]++;
                q[++r]=e[i].n;
            }
        }
    }
}
void isap(int x)
{
    bfs(x);
    int s=1;
    int pre[1005];
    memset(pre,-1,sizeof(pre));
    int cur[1005];
    for(int i=1;i<=x;i++)
        cur[i]=head[i];
    while(d[1]<=x)
    {
        if(s==x)
        {
            long long minn=123456789000000;
            int p=pre[s];
            while(~p)
            {
                minn=min(minn,e[p].v);
                p=pre[e[p^1].n];
            }
            sum+=minn;
            p=pre[s];
            while(~p)
            {
                e[p].v-=minn;
                e[p^1].v+=minn;
                p=pre[e[p^1].n];
            }
            s=1;
        }
        int flag=0;
        for(int i=cur[s];~i;i=e[i].nxt)
            if(e[i].v&&d[e[i].n]+1==d[s])
            {
                pre[e[i].n]=i;
                cur[s]=e[i].nxt;
                flag=1;
                s=e[i].n;
                break;
            }
        if(flag==0)
        {
            int tmp=d[s];
            d[s]=x+1;
            for(int i=head[s];~i;i=e[i].nxt)
                if(e[i].v)
                    d[s]=min(d[s],d[e[i].n]+1);
            gap[tmp]--;
            gap[d[s]]++;
            if(gap[tmp]==0)
                return;
            cur[s]=head[s];
            if(s!=1)
                s=e[pre[s]^1].n;
        }
    }
}
}
int main()
{
    using namespace graph;
    init();
    Flow::init();
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int i=1;i<=n;i++)
        scanf("%lld",&flow[i]);
    flow[1]=12345678900000000;
    flow[n]=12345678900000000;
    spfa(1);
    spfa(n);
    for(int i=1;i<=n;i++)
    {
        Flow::add(i,500+i,flow[i]);
        for(int j=head[i];~j;j=e[j].nxt)
            if(dis[0][i]+e[j].v+dis[1][e[j].n]==dis[0][n])
                Flow::add(500+i,e[j].n,12345678900000000);
    }
    Flow::isap(500+n);
    printf("%lld\n",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
更多阅读
标签云
DP gcd/lcm KMP LCA lct splay tarjan 二分答案 二进制 倍增 前缀和 区间DP 同余 图论 堆 字符串 学习笔记 平衡树 快速排序 拓扑排序 搜索 数列 数学 最小割 最短路 构造 枚举 树 树形DP 树状数组 树链剖分 概率期望 模拟 状态压缩 生成树 线段树 组合数学 网络流 背包 解题报告 计算几何 记录 贪心 递推 随笔
/* */