最小割好劲啊
原题：
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。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≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100
本来想看妹主席的ppt补一波最小割，然后照着ppt上的套路建图，然后连样例都过不了……
然后自己脑补啊，然后脑补出来的图离妹主席的模型越来越远了，最后想到一种建图好像有理有据的样子
测一下样例过了，然后抱着直接WA掉的心态裸交1A……
具体就是先使用最小不能获得的收益转化成最小割模型
然后s到i表示选，i到t表示不选，那么如果把s->i割掉就会损失pi的收益（表示选），把i->t割掉就会损失wi/2的收益（表示不选）
为啥是wi/2？
因为如果a和b有两个都选则获得wi的收益的条件，就会在ab之间连两个方向相反流量为wi/2的边（为啥不是无向边？，因为网络流要建反向边）
然后如果两个都没选那么割掉两个i->t就是少了wi/2*2的收益，如果一个选一个没选那么没选的a就会通过s->a，a->b，b->t割一个wi/2的边，依旧会少wi/2*2的收益
只有当两个都选即s->a，s->b都被割掉的时候a,b之间的边和a,b到t的边才能避免被割掉，获得wi/2*2的收益
（感觉妹主席的方法和我的核心思想是一样的但是在某些细节上不同？反正我A掉了
恩差不多就是酱紫
为了防止精度问题我输入的时候乘个2输出的时候再除回去，不知道这样是否有必要
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int oo=168430090; 8 int rd(){int z=0,mk=1; char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} 10 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 11 return z*mk; 12 } 13 struct ddd{int nxt,y,v,rvs;}e[410000]; int lk[5100],ltp=0; 14 inline void ist(int x,int y,int z){ 15 e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z,e[ltp].rvs=ltp+1; 16 e[++ltp].nxt=lk[y],lk[y]=ltp,e[ltp].y=x,e[ltp].v=0,e[ltp].rvs=ltp-1; 17 } 18 int n,m,a[5100]; int s,t,M=100; 19 int lvl[5100]; 20 int q[5100],hd=0; 21 int quq=0; 22 bool gtlvl(){ 23 memset(lvl,0,sizeof(lvl)); 24 q[hd=1]=s,lvl[s]=1; 25 for(int k=1;k<=hd;++k) 26 for(int i=lk[q[k]];i;i=e[i].nxt)if(e[i].v && !lvl[e[i].y]) 27 lvl[e[i].y]=lvl[q[k]]+1,q[++hd]=e[i].y; 28 return lvl[t]; 29 } 30 int mxflw(int x,int y){ 31 if(x==t) return y; 32 int bwl=0,flw=0; 33 for(int i=lk[x];i && bwl<y;i=e[i].nxt)if(e[i].v && lvl[e[i].y]==lvl[x]+1) 34 if((flw=mxflw(e[i].y,min(y-bwl,e[i].v)))){ 35 bwl+=flw; 36 e[i].v-=flw,e[e[i].rvs].v+=flw; 37 //cout<<x<<"->"<<e[i].y<<" "<<flw<<endl; 38 } 39 if(!bwl) lvl[x]=0; 40 return bwl; 41 } 42 int dnc(){ 43 int bwl=0,flw; 44 while(gtlvl())while(flw=mxflw(s,oo)) bwl+=flw; 45 return bwl; 46 } 47 int main(){//freopen("ddd.in","r",stdin); 48 cin>>n>>m; s=0,t=n+1; 49 for(int i=1;i<=n;++i) ist(s,i,rd()*2); 50 int l,r,v; 51 for(int i=1;i<=m;++i){ 52 l=rd(),r=rd(),v=rd()*2; quq+=v,v>>=1; 53 a[l]+=v,a[r]+=v,ist(l,r,v),ist(r,l,v); 54 } 55 for(int i=1;i<=n;++i) ist(i,t,a[i]); 56 cout<<(quq-dnc())/2<<endl; 57 return 0; 58 }