OJ Board

Code: Select all

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int residue[105][105];
int parent[105];
bool entered[105];
int source, sink, connections;
int maxflow;
int n;

void dfs(int node) {
    int temp; 
    int minm,i;
    if(node==sink) {
        temp=sink;
        minm = 1000000;
        //finding min
        while(temp!=source) {
            if(residue[temp][parent[temp]]<minm) 
                minm=residue[temp][parent[temp]];
            temp=parent[temp];
        }
        maxflow+=minm;
        //cutting my augmenting path
        temp=sink;
        while(temp!=source) {
            residue[temp][parent[temp]]-=minm;
            residue[parent[temp]][temp]-=minm;
            temp=parent[temp];
        }
    return;
    }
    for(i=1;i<=n;i++) if(residue[node][i]>0 && !entered[i]) {
        entered[i]=true;
        parent[i]=node;
        dfs(i);
        entered[i]=false;
    }
}

int main() {
    int i,j;
    int a,b,c;
    int cases=0;
    
    while(scanf("%d",&n)==1) {
        if(!n) break;
        maxflow=0;
        memset(residue,0,sizeof(residue));
        memset(entered,0,sizeof(entered));
        for(i=0;i<connections;i++) {
            if(residue[a][b]==0)
                residue[a][b]=residue[b][a]=c;
            else residue[a][b]=residue[b][a]=residue[a][b]+c;
        }
        parent[source]=0;
        entered[source]=true;        
        dfs(source);
        cout<<maxflow<<endl;
    }
//system("pause");
return 0;
}