[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)

发布于 2018-04-17  74 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)

Description

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另外公司调查得出了所有期望中的用户群,一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci:这些用户会使用中转站Ai和中转站Bi进行通讯,公司可以获益Ci。(1≤i≤M, 1≤Ai, Bi≤N) THU集团的CS&T公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

Tag

网络流

解决思路

把所有收益加起来,将最大获利转化为最小损失。

代码

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

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

const int maxN=505010;
const int maxM=maxN*6;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int n,m,S,T;
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Queue[maxN],Depth[maxN],cur[maxN];

void Add_Edge(int u,int v,int flow);
bool Bfs();
int dfs(int u,int flow);

int main()
{
    ios::sync_with_stdio(false);
    mem(Head,-1);

    cin>>n>>m;S=n+m+1;T=n+m+2;
    for (int i=1;i<=n;i++)
    {
        int C;cin>>C;
        Add_Edge(S,i,C);
    }
    int Ans=0;//建图
    for (int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;Ans+=w;
        Add_Edge(i+n,T,w);
        Add_Edge(u,i+n,inf);Add_Edge(v,i+n,inf);
    }
    //最大流
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) Ans-=di;
    }
    cout<<Ans<<endl;
    return 0;
}

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

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;
    Depth[S]=1;Queue[1]=S;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Depth[E[i].v]==Depth[u]+1))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1497/Luogu4174][NOI2006]最大获利(网络流)


HNCJ OIer 一枚