题目描述
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。 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 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）
题目大意
有N个点，权值（成本）为Pi，M条信息，内容为A,B,C，如果A,B均被选择，则可以获得C的利益。求选择一些点能够得到的最大的利益（获利-成本）。
数据范围
80% n<=200，m<=1000 100% n<=5000,m<=50000,0<=ci<=100,0<=pi<=100
样例输入
5 5 1 2 3 4 5 1 2 3 2 3 4 1 3 3 1 4 2 4 5 3
样例输出
4
解题思路
最大权闭合图 边的事件依赖于两个端点事件的发生，将边事件转为点事件，求解最大权闭合图
代码代码比较丑，凑活着看吧QAQ
#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#define Maxn 55555#define Maxe 555555//数组都是随缘乱开的233using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int S,T,N,dis[Maxn],GAP[Maxn],h[Maxn],cnt=0,Sum=0,m,n;struct node{int to,next,v,pair;}e[Maxe];void AddEdge(int x,int y,int v,int pair){e[cnt]=(node){y,h[x],v,pair};h[x]=cnt;}void AddEdge(int x,int y,int v){if(x==S)Sum+=v;AddEdge(x,y,v,++cnt+1);AddEdge(y,x,0,++cnt-1);}int SAP(int x,int Maxflow){ if(x==T)return Maxflow; int tmp=Maxflow; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; int flow=min(tmp,e[p].v); if(flow&&dis[x]==dis[y]+1){ int ret=SAP(y,flow); tmp-=ret; e[p].v-=ret; e[e[p].pair].v+=ret; if(!tmp||dis[S]==N)return Maxflow-tmp; } } if(--GAP[dis[x]]==0)dis[S]=N; else GAP[++dis[x]]++; return Maxflow-tmp;}int SAP(){ memset(dis,0,sizeof(dis)); memset(GAP,0,sizeof(GAP)); GAP[0]=N; int Ans=0; while(dis[S]<N)Ans+=SAP(S,1<<30); return Ans;}int main(){ n=Getint(),m=Getint(); S=0,T=n+m+1,N=T+1; for(int i=1;i<=n;i++)AddEdge(i+m,T,Getint()); for(int i=1;i<=m;i++){ AddEdge(i,Getint()+m,1<<30); AddEdge(i,Getint()+m,1<<30); AddEdge(S,i,Getint()); } cout<<Sum-SAP(); return 0;}
