二分图的最小点权覆盖问题

这个题最关键的是拆点，对于每一条边u,v，要么选择u-，要么v+，那么对于这个图而言拆点后，每个点分为u+,u-.观察得出，这个图永远是个二分图（按照只有出边还是只有入边分）。所以自然会联想到用最大流求二分图匹配的算法。那么这里显然不是最大流，仔细想想，会发现和最大流的对偶问题——最小割有关。
咋建图呢？可新建一个S，T. S连接所有u- 边权是w- T连接所有u+ 边权是w+ 在原图的每条边上连上正无穷大小边（目的是不让这些边被选为最小割中的边）。然后用dinic跑最小割就行（观察发现所有的割边都是S,u or u,T ，而这些边的权值已经被赋值成了w- or w+ ，而原图中每一条边都会被算在最小割里面，实现了原问题与最小割的一一对应）

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=100*2+10,M=(5010+N*2)*2+110;

int w1[N],w2[N];

int q[N],d[N],cur[N],h[N],f[M],idx,n,m,e[M],ne[M],S,T;

void add(int a,int b,int c)
{
  //  cout<<a<<"fuck " <<b<<' '<<c<<endl;
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int hh=0,tt=0;
    q[0]=S,cur[S]=h[S],d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
      //  cout<<"now "<<t<<endl;
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
  //  cout<<"fuck" <<u<<endl;
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int r=0,flow;
    while(bfs()) while(flow=find(S,0x3f3f3f3f)) r+=flow;
    //cout<<"ans"<<r<<endl;
    return r;
}

bool st[N];

void dfs(int u)
{
    st[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int ver=e[i];
        if(!st[ver]&&f[i]) dfs(ver);
    }
}

struct E{
    int a,b;
}edge[M];
int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;T=n*2+2,S=n*2+1;

    for(int i=1;i<=n;i++) scanf("%d",w1+i);

    for(int i=1;i<=n;i++) scanf("%d",w2+i);

    for(int i=1;i<=n;i++) {
        add(S,i+n,w2[i]);
        add(i,T,w1[i]);
    }

    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        edge[i]={a,b};
        add(a+n,b,0x3f3f3f3f);
    }

    cout<<dinic()<<endl;
    dfs(S);

    set<pair<char,int> > s;
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].a,b=edge[i].b;
       // cout<<a<<' '<<b<<endl;
        if(!st[a+n]) s.insert({'-',a});
        else s.insert({'+',b});
    }
    cout<<s.size()<<endl;
    for(auto x:s) cout<<x.se<<' '<<x.fi<<endl;
    return 0;

}