求助,dinic算法,超时
查看原帖
求助,dinic算法,超时
505959
YangJinxi_7_22楼主2022/1/22 22:07
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 4e4 + 5;
const int M = 1e6 + 5;
int n1 , n2 , n3;
int m1 , m2;
int s , t;
int head[N] , cur[N] , tot = 1;
struct edge{
    int to , nxt , wei;
}e[M];
bool vis[N];
int minn[N] , pre[N];
int dep[N];
int ans = 0;

void add( int u , int v , int w ){
    e[++tot].to = v; e[tot].nxt = head[u] ; e[tot].wei = w; head[u] = tot;
    e[++tot].to = u; e[tot].nxt = head[v] ; e[tot].wei = 0; head[v] = tot;
}

bool bfs( ){
    queue<int> q;
    memset( dep , 0 , sizeof( dep ) );
    dep[s] = 1;
    q.push( s );
    while( !q.empty( ) ){
        int u = q.front( );
        q.pop( );
        for( int i = head[u] ; i ; i = e[i].nxt ){
            int v = e[i].to;
            if( !dep[v] && e[i].wei ){
                dep[v] = dep[u] + 1;
                q.push( v );
            }
        }
    }
    if( dep[t] == 0 ) return 0;
    else return 1;
}

int dfs( int u , int dis ){
    if( u == t ) return dis;
    for( int i = cur[u] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( e[i].wei != 0 && ( dep[v] == dep[u] + 1 ) ){
            int di = dfs( v , min( dis , e[i].wei ) );
            if( di > 0 ){
                e[i].wei -= di;
                e[i^1].wei += di;
                return di;
            }
        }
    }
    return 0;
}

int dinic( ){
    int ans = 0;
    while( bfs( ) ){
        for( int i = 0 ; i <= t ; i++ ){
            cur[i] = head[i];
        }
        while( int d = dfs( s , 0x7f7f7f7f ) ){
            ans += d;
        }
    }
    return ans;
}


int main( ) {
    cin >> n1 >> n2 >> n3;
    s = 0;
    t = 2*n1+n2+n3+1;
    for( int i = 1 ; i <= n2 ; i++ ){
        add( s , i , 1 );
    }
    for( int i = 1 ; i <= n1 ; i++ ){
        add( i+n2 , i+n2+n1 , 1 );
    }
    for( int i = 1 ; i <= n3 ; i++ ){
        add( i+2*n1+n2 , t , 1 );
    }
    cin >> m1;
    for( int i = 1 , u , v ; i <= m1 ; i++ ){
        cin >> u >> v;
        add( v , u+n2 , 1 );
    }
    cin >> m2;
    for( int i = 1 , u , v ; i <= m2 ; i++ ){
        cin >> u >> v;
        add( u+n2+n1 , v+2*n1+n2 , 1 );
    }
    cout << dinic( ) <<endl;
    return 0;
}

2022/1/22 22:07
加载中...