为了博多

P2414 - 为了博多

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

Sample Output

1023

Hint

Source

网络流，最大流

每一把刀有3种选择，推6图或者刷大阪城或者与兄弟刀一起，建立源点s，汇点t，从s向所有刀建立一条容量为Xi的边，所有点向t建立一条容量为Yi的边，兄弟刀建立一条容量为w的边。此时的边就有以上三种情况，如果有流从s流到t，这是不允许的(一把刀只能有两种选择);若删掉s与所以要做的就是让s与t不连通，且要剩下的权值最大，就是尽量割掉边权小的边，是的s与t不连通，这就是最小割，所以答案就为所有边的权值（容量）-最小割；

 1 #define ll long long
 2 #define inf 999999999
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<iomanip>
 6 #include<cstring>
 7 #include<cstdlib>
 8 #include<cstdio>
 9 #include<queue>
10 #include<ctime>
11 #include<cmath>
12 #include<stack>
13 #include<map>
14 #include<set>
15 using namespace std;
16 const int maxn=20010+2,maxm=200010+maxn*2;
17 struct E{
18     int fr,to,net,cap,flow;
19 }e[maxm*2];
20 int head[maxn],num_e=-1,n,m,s,t;
21 int a[maxn],pre[maxn],d[maxn];
22 void add(int x,int y,int c) {
23     e[++num_e].to=y,e[num_e].fr=x,e[num_e].cap=c;e[num_e].net=head[x];head[x]=num_e;
24 }
25 int lev[maxn];
26 bool bfs() {
27     memset(lev,0,sizeof(lev));
28     lev[s]=1;
29     queue<int> q;
30     q.push(s);
31     while(!q.empty()) {
32     int u=q.front();q.pop();
33     for(int i=head[u];i!=-1;i=e[i].net)if(!lev[e[i].to]&&e[i].cap>e[i].flow) {
34         lev[e[i].to]=lev[u]+1;
35         q.push(e[i].to);
36         if(e[i].to==t) return true;
37     }
38     }
39     return false;
40 }
41 ll dfs(int u,ll f) {
42     if(u==t) return f;
43     ll tag=0;
44     for(int i=head[u];i!=-1;i=e[i].net)
45     if(lev[e[i].to]==lev[u]+1&&e[i].cap>e[i].flow) {
46         ll c=dfs(e[i].to,min(f-tag,(ll)(e[i].cap-e[i].flow)));
47         e[i].flow += c;
48         e[i^1].flow -= c;
49         tag+=c;
50         if(tag==f) break;
51     }
52     return tag;
53 }
54 ll Dinic() {
55     ll flow=0;
56     while(bfs()) {
57     flow += dfs(s,inf);
58     }
59     return flow;
60 }
61 int main() { 
62     freopen("hakata.in","r",stdin);
63       freopen("hakata.out","w",stdout);
64     memset(head,-1,sizeof(head));
65     cin>>n>>m;int i;s=0,t=n+1;
66     ll sum=0;
67     for(i=1;i<=n;i++) {
68     int cx,cy;scanf("%d%d",&cx,&cy);//  TMD
69     sum += (ll) cx + (ll) cy;
70     add(s,i,cx),add(i,s,0);//  X
71     add(i,t,cy),add(t,i,0);
72     }// 
73     for(i=1;i<=m;i++) {
74     int u,v;scanf("%d%d",&u,&v);int w;scanf("%d",&w);
75     add(u,v,w),add(v,u,w);
76     sum += (ll) w;
77     }
78     printf("%lld",sum-Dinic());
79     return 0;
80 }