题解 P3171 【[CQOI2015]网络吞吐量】 非完美解法

2018-07-07 17:08:39


来发一篇非完美解法的题解;我的博客

非完美解法:

   看到这个题,用网络流来限流当然是第一想法。于是先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,完美解法参考其他dalao的题解。

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)//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]=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("%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;
}