63pts求调
查看原帖
63pts求调
1370077
BoringMax楼主2024/6/5 19:02

6、8、10、11WA了,刚建号下不了数据,也查不出来哪里有问题,求助?

#include <iostream> 
using namespace std;

struct edge{
    int u;
    int v;
};

int flow(int**,int);

int bottleneck(edge *P, int len, int **f, int **Graph){
    for(int i = 0; i <= len; i++){
        int u = P[i].u;
        int v = P[i].v;
        if(Graph[u][v] == f[u][v]){
            return 0;
        }  
    }
    return 1;
}


void augment(int **f, edge *P, int len, int** Graph){
    int b = bottleneck(P,len,f,Graph);
    for(int i = 0; i <= len; i++){
        int u = P[i].u;
        int v = P[i].v;
        if(Graph[u][v] > f[u][v]){
            f[u][v] += b;
        }
        else{
            f[v][u] -= b;
        }
    }
}



void Graph0(int **f, int** Graph, int n, int** Graphf){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(f[i][j] > 0){
                Graphf[i][j] = 0;
                Graphf[j][i] = 1;
            }
            else{
                Graphf[i][j] = Graph[i][j];
            }
        }
    }
}

int dfs(int u, int **Graph, int n, bool* visited, edge *P, int len){
    visited[u] = true;
    for(int v = n-1; v >= 0; v--){
        if(Graph[u][v] > 0 && !visited[v]){
            if(v==n-1){
                P[len].u=u;
                P[len].v=v;
                return len;
            }
            int next = dfs(v,Graph,n,visited,P,len+1);
            if(next){
                P[len].u=u;
                P[len].v=v;
                return next;
            }
        }
    }
    return 0;
}




int findP(int** Graph, int n, edge* P){
    bool* visited = new bool[n];
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }
    int found = dfs(0,Graph,n,visited,P,0);
    delete[] visited;
    return found;
}

void showP(edge* P, int len){
    for(int i = 0; i <= len; i++){
        cout<<P[i].u<<','<<P[i].v<<endl;
    }
}

int** Max_Flow(int** Graph, int n){
    int **Graphf = new int*[n];
    int** f = new int*[n];
    for(int i = 0; i < n; i++){
        Graphf[i] = new int[n];
        f[i] = new int[n];
    }
    edge *P = new edge[n-1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            f[i][j] = 0;
        }
    }
    Graph0(f,Graph,n,Graphf);
    int len = findP(Graphf,n,P);
    while(len){
        augment(f,P,len,Graph);
        Graph0(f,Graph,n,Graphf);
        len = findP(Graphf,n,P);
    }
    for(int i = 0; i < n; i++){
        delete[] Graphf[i];
    }
    delete[] Graphf;
    delete[] P;
    return f;
}

int flow(int** f,int m){
    int maxflow = 0;
    for(int i = 1; i <= m; i++){
        if(f[0][i] > 0){
            maxflow++;
        }
    }
    return maxflow;
}

int main(){
    int n, m;
    cin>>m>>n;
    int N = n+2;
    int** Graph = new int*[N];
    for(int i = 0; i < N; i++){
        Graph[i] = new int[N];
        for(int j = 0; j < N; j++){
            Graph[i][j] = 0;
        }
    }

    int u,v;
    while(1){
        cin>>u>>v;
        if(u == -1 || v == -1){
            break;
        }
        Graph[u][v] = 1;
        Graph[0][u] = 1;
        Graph[v][n+1] = 1;
    }

    int** f = Max_Flow(Graph,N);
    int maxflow = 0;

    for(int i = 1; i <= m; i++){
        if(f[0][i] > 0){
            maxflow++;
        }
    }
    cout<<maxflow<<endl;
    for(int i = 1; i <= m; i++){
        if(f[0][i] > 0){
            cout<<i<<' ';
            for(int j = m+1; j <= n; j++){
                if(f[i][j] > 0){
                    cout<<j<<endl;
                    break;
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        delete[] Graph[i];
        delete[] f[i];
    }
    delete[] Graph;
    delete[] f;
}

2024/6/5 19:02
加载中...