萌新刚学网络流求助

Dr_Gilbert @ 2022-05-26 21:40:39

by platelett @ 2022-05-26 21:48:02

改了一个小地方，再交试试？

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int M=2.5e5+10;
const int INF=0x7fffffff;
struct edge{
    int v,val,ops;
}e[M<<2];
int dis[N],st[N],n,m,s,t,tot;
vector<vector<int>> G;
bool bfs(){
    memset(dis,0,sizeof(dis));
    queue<int> que;que.push(s);
    dis[s]=1;
    while (que.size()){
        int x=que.front();
        que.pop();
        for (int id:G[x]){
            auto p=e[id];
            int v=p.v,w=p.val;
            if (w&&!dis[v]){
                st[x]=0;
                dis[v]=dis[x]+1;
                que.push(v); 
            }
        }
    }
    return dis[t];
}
int dinic(int x, int in){
    if (x==t) return in;
    int out=0;
    for (int i=st[x];i<G[x].size();i++){
        int id=G[x][i];auto p=e[id];
        int v=p.v,w=p.val,ops=p.ops;
        st[x]=i;
        if (dis[x]+1==dis[v]&&w>0){
            int tmp=dinic(v,min(w,in));
            in-=tmp;out+=tmp;
            e[id].val-=tmp;e[ops].val+=tmp;
            if(!in) break;
        }
    }
    if (!out) dis[x]=0;
    return out;
}
void add(int u,int v,int w){
    e[tot+1]={v,w,tot+2};
    e[tot+2]={u,0,tot+1};
    G[u].push_back(tot+1);
    G[v].push_back(tot+2);
    tot+=2;return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);cout.tie(nullptr); 
    int e;cin>>n>>m>>e;
    G.resize(n+m+10);s=0,t=n+m+1;
    for (int i=1;i<=e;i++){
        int u,v;cin>>u>>v;
        add(u,v+n,1);
    }
    for (int i=1;i<=n;i++) add(s,i,1);
    for (int i=1;i<=m;i++) add(n+i,t,1); 
    int maxflow=0;
    while (bfs()){
        maxflow+=dinic(s,INF);
//      cout<<maxflow<<endl;
    }
    cout<<maxflow;
    return 0;
}

by Dr_Gilbert @ 2022-05-26 21:51:18

@plate_let 谢谢您，过了。