为了博多

Description

做了个噩梦，梦见我的 n 把刀到60级会二次变身，变成一个 对推6图有xi点贡献，刷大阪城有yi点贡献 的刀，于是要把刀分成两队一队刷大阪城另一队推6图 。 

但是有m对兄弟刀在同一队会有特殊的buff加成，加成值为wi，问怎样分队收益最大，最大值是多少。

Input

第一行两个整数n（刀的数目）(0<=n<=20000)，m（兄弟刀的对数）(0<=m<=200000) 

接下来n行，每行两个整数xi，yi，分别表示第i把刀对推6图的贡献xi和对刷大阪城的贡献yi。 

接下来m行，每行三个整数u，v，wi，分别表示第u把刀和第v把刀是兄弟刀，在一队能产生wi的buff值。

Output

一行一个数字，表示最大收益

Sample Input

3 1 

1 10 

2 10 

10 3 

2 3 1000

Sample Output

1023

题解:

不同寻常的思维:

用的是最大权闭合子图的思想,直接用总收益减掉不合法的,建边比较巧妙.

对于每一个点(S,i,xi) (i,T,yi)

对于每一组关联:(x,y,wi) 建双向边

哪一个损失小就割在哪条边

答案就是sum-最小割

1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #define RG register
 8 using namespace std;
 9 typedef long long ll;
10 const int N=20005,M=200005,INF=2e9;
11 int head[N],num=1;
12 struct Lin{
13     int next,to,dis;
14 }a[(M+N)<<2];
15 void init(int x,int y,int z){
16     a[++num].next=head[x];a[num].to=y;a[num].dis=z;head[x]=num;
17 }
18 void addedge(int x,int y,int z){
19     init(x,y,z);init(y,x,0);
20 }
21 int gi(){
22     int str=0;char ch=getchar();
23     while(ch>'9' || ch<'0')ch=getchar();
24     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
25     return str;
26 }
27 int n,m,S=0,T,q[N],dep[N];
28 bool bfs(){
29     memset(dep,0,sizeof(dep));
30     RG int x,u,t=0,sum=1;
31     q[1]=S;dep[S]=1;
32     while(t!=sum){
33         x=q[++t];
34         for(RG int i=head[x];i;i=a[i].next){
35             u=a[i].to;
36             if(dep[u] || a[i].dis<=0)continue;
37             dep[u]=dep[x]+1;q[++sum]=u;
38         }
39     }
40     return dep[T];
41 }
42 int dfs(int x,int flow){
43     if(x==T || !flow)return flow;
44     int tot=0;int tmp,u;
45     for(RG int i=head[x];i;i=a[i].next){
46         u=a[i].to;
47         if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue;
48         tmp=dfs(u,min(flow,a[i].dis));
49         tot+=tmp;flow-=tmp;
50         a[i].dis-=tmp;a[i^1].dis+=tmp;
51         if(!flow)break;
52     }
53     if(!tot)dep[x]=0;
54     return tot;
55 }
56 int maxflow(){
57     int tot=0,tmp;
58     while(bfs()){
59         tmp=dfs(S,INF);
60         while(tmp)tot+=tmp,tmp=dfs(S,INF);
61     }
62     return tot;
63 }
64 void work(){
65     n=gi();m=gi();T=n+1;
66     int x,y,z;ll ans=0;
67     for(RG int i=1;i<=n;i++){
68         x=gi();y=gi();
69         addedge(S,i,x);addedge(i,T,y);
70         ans+=x+y;
71     }
72     for(RG int i=1;i<=m;i++){
73         x=gi();y=gi();z=gi();
74         addedge(x,y,z);addedge(y,x,z);
75         ans+=z;
76     }
77     ans=ans-maxflow();
78     printf("%lld\n",ans);
79 }
80 int main()
81 {
82     freopen("hakata.in","r",stdin);
83     freopen("hakata.out","w",stdout);
84     work();
85     return 0;
86 }