柒葉灬 的博客

柒葉灬 的博客

网络流(最大流&费用流)

posted on 2019-07-24 19:19:36 | under 算法学习 |

最大流和费用流的应用


模板:

1.最大流

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1.5e4+100,maxm=5e6+100;
int n,m,k;
int tot=1,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm];
void clear(){
    tot=1;
    memset(head,0,sizeof(head));
}
void add_edge(int u,int v,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
void add_edges(int u,int v,int c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}
int dep[maxn];
queue<int>Q;
int s,t;
bool bfs(){
    while(!Q.empty())Q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1;Q.push(s);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(!dep[y]&&w[i]){
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t];
}
int dfs(int x,int flow){
    if(x==t)return flow;
    int used=0;
    for(int &i=cur[x];i;i=nxt[i]){
        int y=to[i];
        if(w[i]&&dep[y]==dep[x]+1){
            int tmp=dfs(y,min(flow,w[i]));
            w[i]-=tmp;w[i^1]+=tmp;
            used+=tmp;
            flow-=tmp;
            if(flow==0)break;
        }
    }
    if(flow)dep[x]=0;
    return used;
}
long long dinic(){
    long long flow=0;
    while(bfs()){
        for(int i=1;i<=n;i++)
            cur[i]=head[i];
        flow+=dfs(s,2e9);
    }
    return flow;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add_edges(x,y,z);
    }
    cout<<dinic()<<endl;
    return 0;
}

2.最小费用最大流

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl

using namespace std;
const int maxn=1005,maxm=2e5;
int s,t;
int tot=1,head[maxn],to[maxm],nxt[maxm],w[maxm],f[maxm];
void clear(){
    memset(head,0,sizeof(head));
    tot=1;
}
void add_edge(int u,int v,int flow,int cost){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
    w[tot]=cost;
    f[tot]=flow;
}
void add_edges(int u,int v,int flow,int cost){
    add_edge(u,v,flow,cost);
    add_edge(v,u,0,-cost);
}
int dis[maxn],pos[maxn],last[maxn];
bool vis[maxn];
bool spfa(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    memset(last,0,sizeof(last));
    memset(dis,63,sizeof(dis));
    Q.push(s);dis[s]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(f[i]&&dis[y]>dis[x]+w[i]){
                dis[y]=dis[x]+w[i];
                last[y]=x;
                pos[y]=i;
                if(!vis[y]){
                    vis[y]=1;
                    Q.push(y);
                }
            }
        }
    }
    return last[t]>0;
}
void MCMF(){
    int cost=0,flow=0;
    while(spfa()){
        int tmp=2e9;
        for(int x=t;x!=s;x=last[x])
            tmp=min(tmp,f[pos[x]]);

        for(int x=t;x!=s;x=last[x]){
            f[pos[x]]-=tmp;
            f[pos[x]^1]+=tmp;
        }
        flow+=tmp;
        cost+=tmp*dis[t];
    }
}
int main(){
    //连边
    MCMF();
    return 0;
}

题解:

1.方格取数(最大流,最小割)

题意:

给n行m列的矩阵,取出不相邻的若干个数,使得权值和最大。

思路:

最大流流出去的总是权值最小的,这题如果直接写不好写,

考虑换一种方向:

选出去不要哪些点,总和减去这个值就是答案。

代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int rx[]={0,0,1,-1};
const int ry[]={1,-1,0,0};
const int maxn=1e4+100,maxm=1e5;
int n,m,sum,mp[maxn][maxn];
int s,t;
int tot=-1,head[maxn],cur[maxn],to[maxm],nxt[maxm],w[maxm];
void add_edge(int u,int v,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
void add_edges(int u,int v,int c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}
int dep[maxn];
bool bfs(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    for(int i=1;i<=t;i++)
        dep[i]=0;
    Q.push(s);
    dep[s]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=head[x];~i;i=nxt[i]){
            int y=to[i];
            if(dep[y]==0&&w[i]){
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t]!=0;
}
int dfs(int x,int flow){
    if(x==t)return flow;
    for(int &i=cur[x];~i;i=nxt[i]){
        int y=to[i];
        if(dep[y]==dep[x]+1&&w[i]){
            int d=dfs(y,min(flow,w[i]));
            if(d){
                w[i]-=d;
                w[i^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
void dinic(){
    int ans=0;
    while(bfs()){
        for(int i=1;i<=t;i++)
            cur[i]=head[i];
        while(int d=dfs(s,2e9))
            ans+=d;
    }
    cout<<sum-ans<<endl;
}
int ID(int x,int y){
    if(x<1||y<1||x>n||y>m)return -1;
    return (x-1)*m+y;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]),sum+=mp[i][j];
    memset(head,-1,sizeof(head));
    s=n*m+1,t=s+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(i+j&1)add_edges(ID(i,j),t,mp[i][j]);
            else {
                add_edges(s,ID(i,j),mp[i][j]);
                for(int k=0;k<4;k++){
                    int y=ID(i+rx[k],j+ry[k]);
                    if(y==-1)continue;
                    add_edges(ID(i,j),y,2e9);
                }
            }
    dinic();
    return 0;
}

这题用了一个思想:利用网络流求出最小需要舍弃的权值

答案则变为总和减去最小代价

而这种思想就是“最小割”

定义:去除一些边,使得汇点到不了源点。

而最后保留的就是选出最优的答案。

2.餐巾计划(好题,最小费用最大流)

思路1:

处理流量很麻烦,不妨直接设流量就是每天需要之和,

即先买了所有的餐巾,

洗餐巾就相当于退掉,向汇点连边。

思路2:

根据贪心的思路,每天的餐巾买了要么直接洗,要么就一直不洗,

https://cdn.luogu.com.cn/upload/pic/65563.png

下面是思路1的代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=2e3+100,maxm=1e5+100;

int n,P,M,F,N,S;
int s,t;
int A[maxn];
int tot=1,head[maxn],to[maxm],nxt[maxm],f[maxm],w[maxm];
void add_edge(int u,int v,int d,int flow){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=d;
    f[tot]=flow;
    head[u]=tot;
}
void add_edges(int u,int v,int d,int flow){
    add_edge(u,v,d,flow);
    add_edge(v,u,-d,0);
}
int dis[maxn],fa[maxn],last[maxn];
bool vis[maxn];
queue<int>Q;
bool spfa(){
    memset(dis,127,sizeof(dis));
    memset(last,0,sizeof(last));
    while(!Q.empty())Q.pop();
    Q.push(s);dis[s]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(f[i]&&dis[y]>dis[x]+w[i]){
                dis[y]=dis[x]+w[i];
                fa[y]=x;
                last[y]=i;
                if(!vis[y]){
                    vis[y]=1;
                    Q.push(y);
                }
            }
        }
    }
    return last[t];
}
void solve(){
    s=2*n+1;t=2*n+2;
    int cost=0,flow=0;
    for(int i=1;i<=n;i++){
        add_edges(s,i,0,A[i]);
        add_edges(i+n,t,0,A[i]);
        if(i+M<=n)add_edges(i,i+M+n,F-P,2e9);
        if(i+N<=n)add_edges(i,i+N+n,S-P,2e9);

        if(i<n)add_edges(i,i+1,0,2e9);
        else add_edges(i,t,0,2e9);
        cost+=A[i]*P;
    }

    while(spfa()){
        int tmp=2e9;
        for(int i=t;i!=s;i=fa[i]){
            tmp=min(tmp,f[last[i]]);
        }
        for(int i=t;i!=s;i=fa[i]){
            f[last[i]]-=tmp;
            f[last[i]^1]+=tmp;
        }
        cost+=tmp*dis[t];
        flow+=tmp;
    }
    cout<<cost<<endl;
}

int main(){
    cin>>n>>P>>M>>F>>N>>S;
    for(int i=1;i<=n;i++)
        scanf("%d",&A[i]); 
    solve();
    return 0;
}

网络流有很多种做法,

图建的不一样答案一样就可以了。


3.星际转移(最大流)

思路:

对于每一个时间的每一个点建一个点,

如果跑最大流之后流量达不到人数,

说明还需要时间,

那么就继续建新点,连新边,

直到找到最小的时间或者输出-1.

代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1.5e4+100,maxm=5e6+100;
int n,m,k;
int h[25],r[25],num[25][25];
int tot=1,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm];

void add_edge(int u,int v,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
void add_edges(int u,int v,int c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}
int dep[maxn];
queue<int>Q;
int s,t;
bool bfs(){
    while(!Q.empty())Q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1;Q.push(s);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(!dep[y]&&w[i]){
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t];
}
int dfs(int x,int flow){
    if(x==t)return flow;
    for(int &i=cur[x];i;i=nxt[i]){
        int y=to[i];
        if(w[i]&&dep[y]==dep[x]+1){
            int tmp=dfs(y,min(flow,w[i]));
            if(tmp){
                w[i]-=tmp;
                w[i^1]+=tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int dinic(){
    int flow=0;
    while(bfs()){
        for(int i=1;i<=t;i++)
            cur[i]=head[i];
        while(int d=dfs(s,2e9))
            flow+=d;
    }
    return flow;
}

int solve(){
    s=800*(n+2)+1,t=s+1;
    //n+1是月球 n+2是地球 
    int flow=0;
    for(int i=0;i<799;i++){
        add_edges(s,i*(n+2)+n+2,2e9);
        add_edges((i+1)*(n+2)+n+1,t,2e9);
        for(int j=1;j<=m;j++){
            int u=num[j][i%r[j]];
            int v=num[j][(i+1)%r[j]];
            add_edges(i*(n+2)+u,(i+1)*(n+2)+v,h[j]);
        }
        for(int j=1;j<=n+2;j++)
            add_edges(i*(n+2)+j,(i+1)*(n+2)+j,2e9);
        flow+=dinic();
        if(flow>=k)return i+1;
    }
    return 0;
}
int main(){
//  double sz=&cur2-&cur1;
//  cout<<sz/1024/1024<<endl;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&h[i],&r[i]);
        for(int j=0;j<r[i];j++){
            scanf("%d",&num[i][j]);
            if(num[i][j]<=0)num[i][j]+=n+2;
        }
    }
    cout<<solve()<<endl;
    return 0;
}

网络流可以一边跑一边建新边。


4.最长 k 可重区间集(好题,费用流)

思路:

离散化坐标,

然后每两个点之间连上边,

$l[i]$ 与 $r[i]$ 连边,

汇点与 $1$ 连流量为 $K$ 的边

最后跑出来的最小费用的相反数就是最大的答案。

代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl

using namespace std;
const int maxn=1005,maxm=2e5;
int s,t,n,K;
int l[maxn],r[maxn],val[maxn];
int q,C[maxn];

int tot=1,head[maxn],to[maxm],nxt[maxm],w[maxm],f[maxm];
void add_edge(int u,int v,int flow,int cost){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
    w[tot]=cost;
    f[tot]=flow;
}
void add_edges(int u,int v,int flow,int cost){
    add_edge(u,v,flow,cost);
    add_edge(v,u,0,-cost);
}
int dis[maxn],pos[maxn],last[maxn];
bool vis[maxn];
bool spfa(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    memset(last,0,sizeof(last));
    memset(dis,63,sizeof(dis));
    Q.push(s);dis[s]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(f[i]&&dis[y]>dis[x]+w[i]){
                dis[y]=dis[x]+w[i];
                last[y]=x;
                pos[y]=i;
                if(!vis[y]){
                    vis[y]=1;
                    Q.push(y);
                }
            }
        }
    }
    return last[t]>0;
}
void MCMF(){
    int cost=0,flow=0;
    while(spfa()){
        int tmp=2e9;
        for(int x=t;x!=s;x=last[x])
            tmp=min(tmp,f[pos[x]]);

        for(int x=t;x!=s;x=last[x]){
            f[pos[x]]-=tmp;
            f[pos[x]^1]+=tmp;
        }
        flow+=tmp;
        cost+=tmp*dis[t];
    }
    cout<<-cost<<endl;
}
int main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
        if(l[i]>r[i])swap(l[i],r[i]);
        C[++q]=l[i];C[++q]=r[i];
        val[i]=r[i]-l[i];
    }
    sort(C+1,C+1+q);
    q=unique(C+1,C+1+q)-C-1;
    for(int i=1;i<=n;i++){
        l[i]=lower_bound(C+1,C+1+q,l[i])-C;
        r[i]=lower_bound(C+1,C+1+q,r[i])-C;
    }
    s=q+1;t=s+1;
    for(int i=1;i<q;i++)
        add_edges(i,i+1,2e9,0);
    add_edges(s,1,K,0);
    add_edges(q,t,K,0);
    for(int i=1;i<=n;i++){
        add_edges(l[i],r[i],1,-val[i]);
    }
    MCMF();
    return 0;
}

5.太空飞行计划(好题,最大权闭合图)

先介绍一下最大权闭合图什么意思:

给一个有向图,每个点有一个权值,

若选择一个点,那么他的后继节点也都要选,

求最大权值是多少。

思路:

这题若选择了一个任务,

那么所连接的所有器材也都要选上,

任务的权值为正,器材的权值为负,

求得就是最大的利润。

(十分符合最大权闭合图模型)

处理最大权闭合子图:

将源点 $s$ 与所有正权点连边,

将所有负权点与汇点 $t$ 连边,

原图中的所有边变为流量为 $INF$ 的边,

流出的最大流即最小割,即最大权闭合图。

还有个问题就是决策

若源点连向正权值的边流量不为 $0$ ,

则说明这条边没有被割掉,

所以说明这个点要选上,

负权点根据正权点选择搞就行了。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=205,maxm=1e5;
int n,m;
int A[maxn],B[maxn];
int s,t;
int tot,cur[maxn],head[maxn],to[maxm],nxt[maxm],w[maxm];
void clear(){
    memset(head,-1,sizeof(head));
    tot=-1;
}
void add_edge(int u,int v,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
void add_edges(int u,int v,int c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}
int dep[maxn];
bool bfs(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    for(int i=1;i<=t;i++)
        dep[i]=0;
    dep[s]=1;
    Q.push(s);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=head[x];~i;i=nxt[i]){
            int y=to[i];
            if(dep[y]==0&&w[i]){
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t]!=0;
}
int dfs(int x,int flow){
    if(x==t)return flow;
    for(int &i=cur[x];~i;i=nxt[i]){
        int y=to[i];
        if(w[i]&&dep[y]==dep[x]+1){
            int tmp=dfs(y,min(flow,w[i]));
            if(tmp){
                w[i]-=tmp;
                w[i^1]+=tmp;
                return tmp;
            }
        }
    }
    return 0;
}
void dinic(){
    int res=0;
    while(bfs()){
        for(int i=1;i<=t;i++)
            cur[i]=head[i];
        while(int d=dfs(s,2e9))
            res+=d;
    }

}
bool mark[maxn];
void solve(){
    dinic();
    for(int i=1;i<=n+m;i++)
        if(dep[i]){
            mark[i]=1;
        }
    int ans=0;
    for(int i=1,p=0;i<=m;i++){
        if(mark[i]){
            if(p)putchar(' ');
            else p=1;
            printf("%d",i);
            ans+=A[i];
        }
    }
    puts("");
    for(int i=1,p=0;i<=n;i++){
        if(mark[i+m]){
            ans-=B[i];
            if(p)putchar(' ');
            else p=1;
            printf("%d",i);
        }
    }
    puts("");
    printf("%d\n",ans);
}
int main(){
    clear();
    cin>>m>>n;
    s=n+m+1,t=n+m+2;
    for(int i=1;i<=m;i++){
        scanf("%d",&A[i]);
        add_edges(s,i,A[i]);
        char c=' ';
        while(c==' '){
            int res=0;
            while((c=getchar())<48);
            do res=(res<<1)+(res<<3)+(c^48);
            while((c=getchar())>47);
            add_edges(i,res+m,2e9);
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&B[i]);
        add_edges(i+m,t,B[i]);
    }
    solve();
    return 0;
}

6.Harmonious Army(神题,最小割)

题意:

给 $n$ 个点染黑色或白色, $m$ 个关系,若 $u_i$ 与 $v_i$ 都为黑则贡献为 $a_i$ ,若都是白色则为 $c_i$ ,否则是 $b_i$ 。( $b_i=\frac{a_i}{3}+\frac{c_i}{4}$ )

思路:

考虑到正着选不好写,无法转换成最大贡献

应该想到转换为最小割问题,写最小贡献割。

建图确实很神奇,就算想到了最小割也不一定会写,

图建出来为下图所示:

对于一对关系有四种割法,正好可以对应 $4$ 种选择,

$$ a+b=B+C $$ $$ c+d=A+B $$ $$ a+e+d=b+e+c=A+C $$

解得:

$$ a=b=\frac{B+C}{2} $$ $$ c=d=\frac{A+B}{2} $$ $$ e=-B+\frac{A+C}{2} $$

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=505*2,maxm=1e5;
int n,m,s,t;
int tot,cur[maxn],head[maxn],to[maxm],nxt[maxm];
long long w[maxm];
long long ans,sum[2][maxn];
void clear(){
    memset(sum,0,sizeof(sum));
    memset(head,0,sizeof(head));
    tot=1;ans=0;
}
void add_edge(int u,int v,long long c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
void add_edges(int u,int v,long long c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}
int dep[maxn];
bool bfs(){
    queue<int>Q;
    while(!Q.empty())Q.pop();
    for(int i=1;i<=t;i++)
        dep[i]=0;
    dep[s]=1;
    Q.push(s);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i];
            if(dep[y]==0&&w[i]){
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t]!=0;
}
long long dfs(int x,long long flow){
    if(x==t)return flow;
    for(int &i=cur[x];i;i=nxt[i]){
        int y=to[i];
        if(w[i]&&dep[y]==dep[x]+1){
            int tmp=dfs(y,min(flow,w[i]));
            if(tmp){
                w[i]-=tmp;
                w[i^1]+=tmp;
                return tmp;
            }
        }
    }
    return 0;
}
long long dinic(){
    long long res=0;
    while(bfs()){
        for(int i=1;i<=t;i++)
            cur[i]=head[i];
        while(long long d=dfs(s,2e18))
            res+=d;
    }
    return res;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        clear();
        s=2*n+1;t=s+1;
        for(int i=1,u,v,a,b,c;i<=m;i++){
            scanf("%d%d%d%d%d",&u,&v,&a,&b,&c);
            a<<=1;b<<=1;c<<=1;
            ans+=a+b+c;
            add_edges(u,v,-b+(a+c)/2);
            add_edges(v,u,-b+(a+c)/2);
            sum[0][u]+=(b+c)>>1;
            sum[0][v]+=(b+c)>>1;
            sum[1][u]+=(a+b)>>1;
            sum[1][v]+=(a+b)>>1;
        }
        for(int i=1;i<=n;i++){
            add_edges(s,i,sum[0][i]);
            add_edges(i,t,sum[1][i]);
        }
        printf("%lld\n",(ans-dinic())/2);
    }
    return 0;
}