NOI2006 最大获利

题目:

  新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。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公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

思路:

  像这种有正有负还有相互依赖关系的,还是比较容易想到最大权闭合图上的。虽然我是看标签的
  先把每一个中转站变成一个点,点权为 -p 。再把每个用户群变成一个点,把 c 作为它的点权,再做两条单向边指向 a , b。最大净获利就是最大权了。。。。
  求最大权可以转化成网络流来处理。。。具体方法参考胡泊涛的《最小割模型在信息学竞赛中的应用》。。。

代码:

#include <bits/stdc++.h>
#define MAXN 55005
#define inf 21000000
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
struct Edge{
    int f,t; 
};
vector<Edge> e;
vector<int> mp[MAXN];
int s,t,vis[MAXN];
void addEdge(int a,int b,int f){
    mp[a].push_back(e.size());
    e.push_back((Edge){f,b});
    mp[b].push_back(e.size());
    e.push_back((Edge){0,a});
}
bool bfs(){
    queue<int> q;
    mset(vis,0);
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int a=q.front();
        for(int i=0;i<mp[a].size();i++){
            Edge et=e[mp[a][i]];
            if(et.f&&!vis[et.t]){
                vis[et.t]=vis[a]+1;
                q.push(et.t);
                if(et.t==t)
                    return true;
            }
        } 
        q.pop();
    }
    return false;
}
int dfs(int d,int maxn){
    int ans=0;
    if(d==t)
        return maxn;
    if(!maxn)
        return 0;
    for(int i=0;i<mp[d].size();i++){
        Edge et=e[mp[d][i]];
        if(vis[et.t]==vis[d]+1&&et.f){
            int w=dfs(et.t,min(maxn,et.f));
            e[mp[d][i]].f-=w;
            e[mp[d][i]^1].f+=w;
            ans+=w;
            maxn-=w;
            if(!maxn)
                return ans;
        }
    }
    if(!ans)
        vis[d]=-1;
    return ans;
}
int main(){
    int n,m,ans=0,sum=0;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    s=n+m+1;t=n+m+2;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        a=-a;
        if(a>0){
            addEdge(s,i,a);
            sum+=a;
        }
        else 
            addEdge(i,t,-a);
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c>0){
            addEdge(s,i+n,c);
            addEdge(i+n,a,inf);
            addEdge(i+n,b,inf);
            sum+=c;
        }
        else {
            addEdge(i+n,t,-c);
            addEdge(i+n,a,inf);
            addEdge(i+n,b,inf);
        }
    }
    while(bfs())
        ans+=dfs(s,inf);
    cout<<sum-ans<<endl;
    return 0;
}