Maxflow－Deja Vu｜痞客邦

很多多餘的程式碼

因為懶得改又得趕著交作業

留下來以後就可以慢慢改了

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <cmath>
#include <ctime>

#define MAX 100
#define white 0
#define black 1

// structure definition
struct Node {
   long id;
   long value;
}; // end struct Time

void createAdjList( Node **Adj, long numberOfNodes, long degree[] );
int fordfulkerson( Node **Adj, long numberOfNodes, long degree[], long maxflow,long COLOR[],long pi[],long d[],long Q[] );
bool BFS( Node **Adj, long numberOfNodes,long degree[],long COLOR[],long pi[],long d[],long Q[]);
//void printAdjList(Node **Adj,long numberOfNodes,long pi[] ,long d[] ,long degree[]);

long flow[MAX][MAX];
long capacity[MAX][MAX];

int main()
{
/*while(1)
{////*////
long numberOfNodes,maxflow;
long time1, time2;

srand( time(0) );

do {
cout << "How many nodes( nodes at least 10 )? ";
cin >> numberOfNodes;
} while( numberOfNodes <= 2);
cout << endl;

time1 = time(0);

long *degree = new long[ numberOfNodes + 1 ];
long *d = new long[ numberOfNodes + 1 ];
// long *color = new long[ numberOfNodes + 1 ];
long *pi = new long[ numberOfNodes + 1 ];
long *Q = new long[numberOfNodes + 1 ];
long *COLOR = new long[numberOfNodes+1];

// Node **Adj = new Node*[ numberOfNodes + 1 ];
Node **Adj;
Adj = new Node*[ numberOfNodes + 1 ];

maxflow = 0;

createAdjList( Adj, numberOfNodes, degree );

// BFS( Adj,numberOfNodes,degree,COLOR,pi,d,Q );

//fordfulkerson( Adj,numberOfNodes,degree,maxflow,COLOR,pi,d,Q);

cout<<endl<<"Max-Flow: "<<fordfulkerson( Adj,numberOfNodes,degree,maxflow,COLOR,pi,d,Q)<<endl;

// printAdjList(Adj, numberOfNodes, pi , d ,degree);
cout<<endl;
time2 = time(0);
cout << time2 - time1 << " seconds" << endl << endl;

delete [] degree;
delete [] pi;
for( long i = 1; i <= numberOfNodes; i++ )
delete [] Adj[i];
delete [] Adj;
//}/////////
/*char ch;
cout << "Press any key to continue";
ch = cin.get();
ch = cin.get();*/
system("pause");

return 0;

} // end main

void DFSVISIT(Node **Adj, long numberOfNodes,Node color[],long u,long degree[])
{
color[u].value = 1;
for(long i = 1;i<=degree[u];i++)
{
if( color[Adj[u][i].id].value == 0 )
DFSVISIT(Adj,numberOfNodes,color,Adj[u][i].id,degree);
}
}

void DFS(Node **Adj, long numberOfNodes,Node color[],long degree[])
{

for(long i = 1;i<=numberOfNodes;i++)
color[i].value = 0;

if( color[1].value == 0 )
DFSVISIT(Adj,numberOfNodes,color,1,degree);

}

void createAdjList( Node **Adj, long numberOfNodes, long degree[] )
{
long i,j,k,p,realdegree;
long numberOfEdges = 0;
// long degreeUpperBound = static_cast<long>(log10(numberOfNodes));
long degreeUpperBound = static_cast<long>(sqrt(numberOfNodes));
long *array = new long[numberOfNodes + 1 ];
Node *color = new Node[numberOfNodes + 1 ];

srand( time(0) );

for( i = 1; i <= numberOfNodes; i++ ) {
  degree[i] = rand() % degreeUpperBound + 1;
  realdegree = degree[1];
  numberOfEdges += degree[i];

}

// cout << "\nThe graph has " << numberOfEdges << " edges.\n";

for(i = 1;i<=numberOfNodes;i++)
{
array[i] = i;
}
Adj[1] = new Node[numberOfNodes + 1];

for( i = 1; i <= numberOfNodes; i++ )
{

if( i>1 )
Adj[i] = new Node[ degree[i] + 1 ];

  p = numberOfNodes;

   //cout<<i<<"-> ";
   for( j = 1; j <= degree[i] ; j++)
   {

    k = rand() % p + 1;

    while(i==k)
    {
     k = rand() % p + 1;
    }

Adj[i][j].id = array[k];

    if( k!=p )
    {
     if( p==i )
     {
      array[k] = array[p-1];
      p--;
     }
     else
     array[k] = array[p];
    }
    p--;

// Adj[i][j].weight = rand() % weightUpperBound + 1; //放入weight arrary亂數值且不超過weightUpperBound

// cout<<" ("<<Adj[i][j].id<<" , "<<Adj[i][j].weight<<")";

}

   //cout<<endl;
   for(long k = 1;k<=numberOfNodes;k++)
   {
    array[k] = k;
   }

}

DFS(Adj,numberOfNodes,color,degree);

for(long s = 1;s<=numberOfNodes;s++)
{
  if( color[s].value == 0 )
  {
   realdegree++;
   Adj[1][realdegree].id = s;
   //Adj[1][realdegree].weight = rand() % weightUpperBound + 1;
  }
}
degree[1] = realdegree;

/*for( i = 1; i <= numberOfNodes; i++ )
{
cout<<i<<"-> ";

  for( j = 1; j <= degree[i]; j++)
  {
   cout<<" ("<<Adj[i][j].id<<" , "<<Adj[i][j].weight<<")";
  }
  cout<<endl;

}*/

}

void Enqueue( long Q[], long s ,long &tail ,long numberOfNodes)
{
Q[tail] = s;

if( tail == numberOfNodes )
tail = 1;
else
tail++;

}

int Dequeue( long Q[],long &head, long numberOfNodes )
{
long s;

s = Q[head];

if( head == numberOfNodes )
head = 1;
else
head++;

return s;
}

bool BFS( Node **Adj, long numberOfNodes,long degree[],long COLOR[],long pi[],long d[],long Q[])
{

long s,tail,head,u,i,j,v;

tail = 1;
head = 1;
s = 1;

for( i = 1;i<=numberOfNodes;i++)
{
  for(j = 1;j<=degree[i];j++)
  {
   COLOR[Adj[i][j].id] = white;
  }
}

d[s] = 0;
pi[s] = 0;
COLOR[s] = black;
Enqueue(Q,s,tail,numberOfNodes);

while( head != tail )
{
u = Dequeue(Q,head,numberOfNodes);

  for(v=1;v<=degree[u];v++)
  {
   if( COLOR[Adj[u][v].id] == white && capacity[u][Adj[u][v].id]-flow[u][Adj[u][v].id]>0 )
   {
    COLOR[Adj[u][v].id] = black;
    d[Adj[u][v].id] = d[u] + 1;
    pi[Adj[u][v].id] = u;
    Enqueue(Q,Adj[u][v].id,tail,numberOfNodes);
   }
  }
}

if( COLOR[numberOfNodes]==black )
return true;
else
return false;

}

int min( int a , int b )
{
return a<b ? a:b;
}

int fordfulkerson( Node **Adj, long numberOfNodes, long degree[], long maxflow,long COLOR[],long pi[],long d[],long Q[])
{
int i,j,cf,u,capacityUpperBound;

capacityUpperBound = 30;
cf = 100000;

for(i = 1;i<=numberOfNodes;i++)
{
  for(j=1;j<=degree[i];j++)
  {
   capacity[i][Adj[i][j].id] = rand() % capacityUpperBound + 1;
   flow[i][Adj[i][j].id] = 0;
   flow[Adj[i][j].id][i] = 0;
  }
}

for( i = 1; i <= numberOfNodes; i++ )
{
cout<<i<<"-> ";

  for( j = 1; j <= degree[i]; j++)
  {
   cout<<" ("<<Adj[i][j].id<<" , "<<capacity[i][Adj[i][j].id]<<")";
  }
  cout<<endl;

}

while( BFS(Adj,numberOfNodes,degree,COLOR,pi,d,Q) )
{
  u = numberOfNodes;
  do
  {
   cf = min( cf , capacity[pi[u]][u]-flow[pi[u]][u]);
   u = pi[u];
  }while( pi[u] > 0 );

u = numberOfNodes;

  do
  {
   flow[pi[u]][u] += cf;
   flow[u][pi[u]] -= cf;
   u = pi[u];
  }while( pi[u] > 0 );

maxflow+=cf;
}

return maxflow;
}

///////////////// for BFS test!! ////////////////////////////////////////////
/*void printAdjList(Node **Adj,long numberOfNodes,long pi[] ,long d[] ,long degree[])
{
cout<<endl<<"d :"<<endl;
for( int i = 1;i<=numberOfNodes;i++ )
{
cout<<"d["<<i<<"] = "<<d[i]<<endl;
}

cout<<endl<<"parent :"<<endl;

for(int j = 1;j<=numberOfNodes;j++)
{
cout<<"pi["<<j<<"] = "<<pi[j]<<endl;
}
}*/