洛谷P1345

P1345 [USACO5.4]奶牛的电信Telecowmunication

转化为最小割，注意起始点为i+n

const int N=12000+96;
struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
    e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,s,su,lv[N];

int bfs(){
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd)); // 当前弧优化初始化
    queue<int> q;
    q.push(s);
    lv[s]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1,q.push(to);
            }
        }
    }
    return  lv[n];
}

int dfs(int p,int flow){
    if(p==n)
    return flow;
    int r=flow;
    for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol&&lv[to]==lv[p]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>su>>m>>s>>n;
    s+=su;
    f(i,1,su)
    {
    add( i, i+su, 1 ) ; add( i+su, i, 0 ) ;
    }
    f(i,1,m){
        int aa,bb;
        cin>>aa>>bb;
        add(aa+su,bb,1);
        add(bb,aa+su,0);  
        add(bb+su,aa,1);
        add(aa,bb+su,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(s,3e8);
    }
   cout<<ans;
    return 0;
}