【CJOJ】为了博多

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

题解：显然一道最小割的题目，最好收入的一般套路就是sum减去最小割，然而最重要的是想清楚怎么建图，我们可以思考s为推6图，t为大阪城，将每个节点和s，t连对应权值的边，如果i和j之间有对应关系时就连一条双向边，这个图就可以满足题目的所以关系。选t就割和s的连边，选s就割和t的连边，如果同时刷的话中间的权显然就都得到了，如果分开刷的话，就需要把中间的也割掉，这样就形成割了。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<algorithm>

#include<queue>

#include<cstring>

const int MAXN=;

using namespace std;

struct edge{

    int first;

    int next;

    int cap;

    int to;

}a[MAXN];

int dis[MAXN],n,m,sum=,num=;

int s,t;

queue<int> q;

void addedge(int from,int to,int cap){

    a[++num].to=to;

    a[num].cap=cap;

    a[num].next=a[from].first;

    a[from].first=num;

}

void link(int x,int y,int cap){

    addedge(x,y,cap),addedge(y,x,);

}

bool bfs(){

    while(!q.empty()) q.pop();

    memset(dis,,sizeof(dis));

    dis[s]=;q.push(s);

    while(!q.empty()){

        int now=q.front();

        q.pop();

        for(int i=a[now].first;i;i=a[i].next){

            int to=a[i].to;

            if(dis[to]==&&a[i].cap>){

                dis[to]=dis[now]+;

                q.push(to);

                if(to==t) return ;

            }

        }

    }

    return ;

}

int dfs(int now,int flow){

    if(now==t) return flow;

    int tag=;

    for(int i=a[now].first;i;i=a[i].next){

        int to=a[i].to;

        if(dis[to]==dis[now]+&&a[i].cap>){

            int minn=dfs(to,min(a[i].cap,flow-tag));

            a[i].cap-=minn;

            a[i^].cap+=minn;

            tag+=minn;

            if(tag==flow) return tag;

        }

    }

    return tag;

}

int dinic(){

    int max_flow=;

    while(bfs()) max_flow+=dfs(s,<<);

    return max_flow;

}

int main(){

    scanf("%d%d",&n,&m);s=,t=n+;

    for(int i=;i<=n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        sum+=(x+y);

        link(,i,x),link(i,t,y);

    }

    for(int i=;i<=m;i++){

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        link(x,y,z);link(y,x,z);

        sum+=z;

    }

    printf("%d",sum-dinic());

    return ;

}

代码：

巴特西