[模拟赛FJOI Easy Round #2][T3 skill] (最小割+最大权闭合子图（文理分科模型）)

2 1
50 5
10 20
1 2 100 50 50

125

#include<stdio.h>
#include<limits.h>
#include<string.h>
#define LL long long
#define dmin(a,b) ((a)<(b)?(a):(b))
inline int Rin(){
    int x=0,c=getchar(),f=1;
    for(;c<48||c>57;c=getchar())
        if(!(c^45))f=-1;
    for(;c>47&&c<58;c=getchar())
        x=(x<<1)+(x<<3)+c-48;
    return x*f;
}
const int N=500010;
const int M=40010;
const LL LINF=LONG_LONG_MAX/3*2;
LL tot(0);
int n,m,S,T,ecnt=1,fst[N+M*2];
struct edge{
    int u,v,nxt;
    LL cap,flow;
}e[(6*M+2*N)*2];
inline void link(int x,int y,LL w){
    e[++ecnt].u=x;e[ecnt].v=y;
    e[ecnt].cap=w;e[ecnt].flow=0;
    e[ecnt].nxt=fst[x];fst[x]=ecnt;
    e[++ecnt].u=y;e[ecnt].v=x;
    e[ecnt].cap=0;e[ecnt].flow=0;
    e[ecnt].nxt=fst[y];fst[y]=ecnt;
}
bool vis[N+M*2];
int num[N+M*2],cur[N+M*2],d[N+M*2],p[N+M*2],q[N+M*2];
void bfs(){
    int hd=0,tl=1;
    q[0]=T;d[T]=0;vis[T]=true;
    while(hd^tl){
        int now=q[hd++];
        for(int j=fst[now];j;j=e[j].nxt)
            if(!vis[e[j].u] && e[j].cap>e[j].flow)
                vis[e[j].u]=true,
                d[e[j].u]=d[now]+1,
                q[tl++]=e[j].u;
    }
}
inline LL Agument(){
    LL a=LINF;
    int x=T;
    while(x^S)
        a=dmin(a,e[p[x]].cap-e[p[x]].flow),
        x=e[p[x]].u;
    x=T;
    while(x^S)
        e[p[x]].flow+=a,
        e[p[x]^1].flow-=a,
        x=e[p[x]].u;
    return a;
}
LL ISAP(){
    int x(S);
    LL flow(0);
    bfs();
    for(int i=S;i<=T;i++)num[d[i]]++;
    for(int i=S;i<=T;i++)cur[i]=fst[i];
    while(d[S]<T){
        if(!(x^T))
            flow+=Agument(),
            x=S;
        bool advanced=false;
        for(int j=cur[x];j;j=e[j].nxt)
            if(e[j].cap>e[j].flow && d[x]==d[e[j].v]+1){
                advanced=true;
                cur[x]=j;
                p[e[j].v]=j;
                x=e[j].v;
                break;
            }
        if(!advanced){
            int mn=T-1;
            for(int j=fst[x];j;j=e[j].nxt)
                if(e[j].cap>e[j].flow)
                    mn=dmin(mn,d[e[j].v]);
            if(--num[d[x]]==0)break;
            num[d[x]=mn+1]++;
            cur[x]=fst[x];
            if(x^S)x=e[p[x]].u;
        }
    }
    return flow;
}
int main(){
    freopen("skill.in","r",stdin);
    freopen("skill.out","w",stdout);
    n=Rin(),m=Rin();
    S=1,T=n+1+m*2+1;
    for(int i=1;i<=n;i++){
        LL ap=Rin(),ad=Rin();
        tot+=ap+ad;
        link(S,i+1,ap);
        link(i+1,T,ad);
    }
    for(int i=1;i<=m;i++){
        int u=Rin(),v=Rin();
        LL AP=Rin(),AD=Rin(),AX=Rin();
        tot+=AP+AD;
        link(u+1,v+1,AX);
        link(v+1,u+1,AX);
        link(S,n+1+i,AD);
        link(n+1+i,u+1,LINF);
        link(n+1+i,v+1,LINF);
        link(n+1+i+m,T,AP);
        link(u+1,n+1+i+m,LINF);
        link(v+1,n+1+i+m,LINF);
    }
    printf("%I64d\n",tot-ISAP());
    fclose(stdin);
    fclose(stdout);
    return 0;
}