為了博多

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 }