題目描述
新的技術正沖擊著手機通訊市場，對于各大運營商來說，這既是機遇，更是挑戰。 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;}
