ネットワークフロー


1.最大ストリーム
  • EK
    struct edge
    {
    int from, to, cap, flow;//     ,  ,  ,  
    edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f){}
    };
    int n, m;//n   ,m   
    vectore;//        
    vectorG[maxn];//   ,G[i][j]    i  j   e       
    int a[maxn];//          
    int p[maxn];//p[i]   s   t   i        
    void init(int n)
    {
    for(int i = 0; i <= n; i++)G[i].clear();
    e.clear();
    }
    void addedge(int u, int v, int c)
    {
    e.push_back(edge(u, v, c, 0));//   
    e.push_back(edge(v, u, 0, 0));//   ,   0
    m = e.size();
    G[u].push_back(m - 2);
    G[v].push_back(m - 1);
    }
    int EK(int s, int t)//   s,   t
    {
    int flow = 0;
    for(;;)
    {
        memset(a, 0, sizeof(a));//   s    ,          0
        queueQ;//BFS    
        Q.push(s);
        a[s] = INF;//       INF
        while(!Q.empty())
        {
            int x = Q.front();//          
            Q.pop();
            for(int i = 0; i < G[x].size(); i++)//      
            {
                edge& now = e[G[x][i]];
                if(!a[now.to] && now.cap > now.flow)
                    //a[i] 0  i     
                    //now.cap > now.flow          
                    //         ,         
                {
                    p[now.to] = G[x][i];//      
                    a[now.to] = min(a[x], now.cap - now.flow);
                    //                             ,       
                    Q.push(now.to);//         
                }
            }
            if(a[t])break;//         t,        
        }
        if(!a[t])break;//          ,       ,         ,      
        for(int u = t; u != s; u = e[p[u]].from)//      
        {
            e[p[u]].flow += a[t];//                    
            e[p[u]^1].flow -= a[t];//                    
        }
        flow += a[t];//              
    }
    return flow;
    }
    //  
    #include
    #include
    #include
    #include
    using namespace std;
    const int INF=0x7ffffff;
    queue  q;
    int n,m,x,y,s,t,g[201][201],pre[201],flow[201],maxflow; 
    //g      ,pre           ,flow          
    inline int bfs(int s,int t)
    {
    while (!q.empty()) q.pop();
    for (int i=1; i<=n; i++) pre[i]=-1;
    pre[s]=0;
    q.push(s);
    flow[s]=INF;
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        if (x==t) break;
        for (int i=1; i<=n; i++)
          //EK          
          if (g[x][i]>0 && pre[i]==-1)
          {
            pre[i]=x;
            flow[i]=min(flow[x],g[x][i]);
            q.push(i);
          }
    }
    if (pre[t]==-1) return -1;
    else return flow[t];
    }
    //increase       
    void EK(int s,int t)
    {
    int increase=0;
    while ((increase=bfs(s,t))!=-1)//        !Tle 
    {//   
        int k=t;
        while (k!=s)
        {
            int last=pre[k];//       
            g[last][k]-=increase;
            g[k][last]+=increase;
            k=last;
        }
        maxflow+=increase;
    }
    }
    int main()
    {
    scanf("%d%d",&m,&n);
    for (int i=1; i<=m; i++)
    {
        int z;
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=z;//        , += 
    }
    EK(1,n);
    printf("%d",maxflow);
    return 0;
    }
  • Dinic
    #include
    #define me(a,x) memset(a,x,sizeof(a))
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int mod=1e9+7;
    const int N=2e5+5;
    const int MAX=0x7fffffff;
    const int MIN=0x80000000;
    struct Edge{int to,cap,flow,next;}edges[N];
    int head[N],edge_num=0;
    int n,m,s,t;
    int depth[N];//       i    
    void add_edge(int from,int to,int cap,int flow){
    edges[edge_num]={to,cap,flow,head[from]};
    head[from]=edge_num++;
    }
    int DFS(int u,int flow){
    if(u==t)return flow;
    int sum=0,increase;
    for(int i=head[u];~i;i=edges[i].next){
        int v=edges[i].to;
        if(depth[v]==depth[u]+1 and edges[i].cap>edges[i].flow){
            increase=DFS(v,min(flow,edges[i].cap-edges[i].flow));
            flow-=increase;
            sum+=increase;
            edges[i].flow+=increase;
            edges[i^1].flow-=increase; 
            if(flow==0)break;
        }
    }
    return sum;
    }
    bool BFS(){
    me(depth,-1);
    queueQ;
    depth[s]=0;
    Q.push(s);
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        for(int i=head[now];~i;i=edges[i].next){
            int v=edges[i].to;
            if(depth[v]==-1 and edges[i].cap>edges[i].flow){
                depth[v]=depth[now]+1;
                Q.push(v);
            }
        }
    }
    return depth[t]^-1;
    }
    int DINIC(){
    int max_flow=0;
    while(BFS())max_flow+=DFS(s,MAX);
    return max_flow;
    }
    int main(){
    me(head,-1);
    cin>>n>>m>>s>>t;
    for(int i=0;i>u>>v>>cap>>flow;
        add_edge(u,v,cap,flow);
        add_edge(v,u,0,-flow);
    }
    printf("%d
    ",DINIC()); }
  • SAP
    #include
    #define me(a,x) memset(a,x,sizeof(a))
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int mod=1e9+7;
    const int N=505;
    const int INF=0x7fffffff;
    const int SUP=0x80000000;
    struct edge{
    int to,next,cap,flow;
    }edges[N<<2];
    int top,head[N];
    void add_side(int u,int v,int cap,int flow){
    edges[top]=(edge){v,head[u],cap,flow};head[u]=top++;
    edges[top]=(edge){u,head[v],0,-flow};head[v]=top++;
    }
    int n,m,s,t;
    int dis[N],gap[N];
    int dfs(int u,int flow){
    if(u==t)return flow;
    int FLOW=0;
    for(int i=head[u];~i;i=edges[i].next){
        int v=edges[i].to;
        if(dis[u]>dis[v]&&edges[i].cap>edges[i].flow){
            int increase=dfs(v,min(flow-FLOW,edges[i].cap-edges[i].flow));
            FLOW+=increase;
            edges[i].flow+=increase;
            edges[i^1].flow-=increase;
            if(FLOW==flow)return FLOW;
        }
    }
    if(!(--gap[dis[u]]))dis[s]=n+1;
    gap[++dis[u]]++;
    return FLOW;
    }
    int ISAP(){
    int flow=0;gap[0]=n;
    while(dis[s]>T;
    for(int cas=1;cas<=T;cas++){
        init();
        scanf("%d%d",&n,&m);
        for(int i=0;i
  • ISAP
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    const int inf=1e9;
    int m,n,s,t,maxflow=0,head[50000],num_edge=-1;
    int cur[50000],deep[50000],last[50000],num[50000];
    //cur     ; last       ; num    GAP   
    struct Edge{
    int next,to,dis;
    }edge[400000];
    void add_edge(int from,int to,int dis)
    {
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    edge[num_edge].dis=dis;
    head[from]=num_edge;
    }
    //bfs     deep 
    void bfs(int t)
    {
    queueq;
    for (int i=0; i<=n; i++) cur[i]=head[i];
    for (int i=1; i<=n; i++) deep[i]=n;
    deep[t]=0;
    q.push(t);
    while (!q.empty())
    {
        int now=q.front(); q.pop();
        for (int i=head[now]; i!=-1; i=edge[i].next)
        {
            if (deep[edge[i].to]==n && edge[i^1].dis)//i^1       
            {
                deep[edge[i].to]=deep[now]+1;
                q.push(edge[i].to);
            }
        }
    }
    }
    int add_flow(int s,int t)
    {
    int ans=inf,now=t;
    while (now!=s)
    {
        ans=min(ans,edge[last[now]].dis);
        now=edge[last[now]^1].to;
    }
    now=t;
    while (now!=s)
    {
        edge[last[now]].dis-=ans;
        edge[last[now]^1].dis+=ans;
        now=edge[last[now]^1].to;
    }
    return ans;
    }
    void isap(int s,int t)
    {
    int now=s;
    bfs(t);//       
    for (int i=1; i<=n; i++) num[deep[i]]++;
    while (deep[s]
  • HLPP
    #include
    #include
    #include
    #include
    using std::min;
    using std::vector;
    using std::queue;
    using std::priority_queue;
    const int N=2e4+5,M=2e5+5,inf=0x3f3f3f3f;
    int n,s,t,tot;
    int v[M<<1],w[M<<1],first[N],next[M<<1];
    int h[N],e[N],gap[N<<1],inq[N];//         2n-1 
    struct cmp
    {
    inline bool operator()(int a,int b) const
    {
        return h[a] Q;
    priority_queue,cmp> pQ;
    inline void add_edge(int from,int to,int flow)
    {
    tot+=2;
    v[tot+1]=from;v[tot]=to;w[tot]=flow;w[tot+1]=0;
    next[tot]=first[from];first[from]=tot;
    next[tot+1]=first[to];first[to]=tot+1;
    return;
    }
    inline bool bfs()
    {
    int now;
    register int go;
    memset(h+1,0x3f,sizeof(int)*n);
    h[t]=0;Q.push(t);
    while(!Q.empty())
    {
        now=Q.front();Q.pop();
        for(go=first[now];go;go=next[go])
            if(w[go^1]&&h[v[go]]>h[now]+1)
                h[v[go]]=h[now]+1,Q.push(v[go]);
    }
    return h[s]!=inf;
    }
    inline void push(int now)//  
    {
    int d;
    register int go;
    for(go=first[now];go;go=next[go])
        if(w[go]&&h[v[go]]+1==h[now])
        {
            d=min(e[now],w[go]);
            w[go]-=d;w[go^1]+=d;e[now]-=d;e[v[go]]+=d;
            if(v[go]!=s&&v[go]!=t&&!inq[v[go]])
                pQ.push(v[go]),inq[v[go]]=1;
            if(!e[now])//            
                break;
        }
    return;
    }
    inline void relabel(int now)//    
    {
    register int go;
    h[now]=inf;
    for(go=first[now];go;go=next[go])
        if(w[go]&&h[v[go]]+1h[now]&&h[i]
    最小分割容量=最大ストリーム=最小パスオーバーライド=|V|-最大独立セット