首页 > ACM题库 > HDU-杭电 > HDU 3879-Base Station-网络流-[解题报告]HOJ
2015
04-13

HDU 3879-Base Station-网络流-[解题报告]HOJ

Base Station

问题描述 :

A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is Pi (1<=i<=n).

When complete building, two places which both have stations can communicate with each other.

Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers Ai, Bi and Ci, which means if place Ai and Bi can communicate with each other, the company will get Ci profit.

Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.

输入:

Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0<n<=5000) and m (0<m<=50000).
The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.

输出:

Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0<n<=5000) and m (0<m<=50000).
The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.

样例输入:

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

样例输出:

4

这题建图自己想了半天搞不懂,然后看了一下别人的建图。。。一脸茫然。。

最后去看了下胡波涛的《最小割模型在信息学竞赛的应用》里面详细的讲解了将最大获利问题转换为最小割模型的过程。

建图:

源点与人连边,容量为获利。站点与汇点连边,容量为耗资。然后是相应的人与其需求的站点连边,容量为无穷。

这样建图就完成了,然后就是找最小割,即割边上的值便为不能获取的利润值,用总值减去得出最大利润。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 60000              //点的个数
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
    int u,v,w,next;
}E[400050];                     //边的个数  记得乘2
int head[MAXN],ecnt;
int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN];
int l,r,mid;
int N,M,scr,sink,vn,num;
void Insert(int u,int v,int w)
{
    E[ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt++;
    E[ecnt].u=v;
    E[ecnt].v=u;
    E[ecnt].w=0;
    E[ecnt].next=head[v];
    head[v]=ecnt++;
}
int Sap(int s,int t,int n)//核心代码(模版)
{
    int ans=0,aug=INF;//aug表示增广路的流量
    int i,v,u=pre[s]=s;
    for(i=0;i<=n;i++)
    {
        cur[i]=head[i];
        dis[i]=gap[i]=0;
    }
    gap[s]=n;
    bool flag;
    while(dis[s]<n)
    {
        flag=false;
        for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定义成int &j,why
        {
            v=E[j].v;
            if(E[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=true;//找到容许边
                aug=min(aug,E[j].w);
                pre[v]=u;
                u=v;
                if(u==t)
                {
                    ans+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        E[cur[u]].w-=aug;
                        E[cur[u]^1].w+=aug;//注意
                    }
                    aug=INF;
                }
                break;//找到一条就退出
            }
        }
        if(flag) continue;
        int mindis=n;
        for(i=head[u];i!=-1;i=E[i].next)
        {
            v=E[i].v;
            if(E[i].w>0&&dis[v]<mindis)
            {
                mindis=dis[v];
                cur[u]=i;
            }
        }
        if((--gap[dis[u]])==0) break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return ans;
}
int n,m;
int main()
{
   while(scanf("%d%d",&n,&m)!=EOF)
   {
       memset(head,-1,sizeof(head));ecnt=0;
       scr=0;sink=n+m+1;vn=sink+1;
       for(int i=1;i<=n;i++)
       {
           int v;
           scanf("%d",&v);
           Insert(i,sink,v);
       }
       int sum=0;
       for(int i=1;i<=m;i++)
       {
           int a,b,v;
           scanf("%d%d%d",&a,&b,&v);
           Insert(scr,i+n,v);
           Insert(i+n,a,INF);
           Insert(i+n,b,INF);
           sum+=v;
       }
        printf("%d\n",sum-Sap(scr,sink,vn));
   }
   return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/amourjun/article/details/9014725


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1