Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  proga
Language: C/C++
Code:
#include "stdio.h"
#include "conio.h"
#include "iostream"
 
using namespace std;
 
#define WHITE 0
#define GREY 1
#define BLACK 2
 
int n,e;
int capacity[100][100], // РњР°С‚рица РїСЂРѕРїСѓСЃРєРЅС‹С… СЃРїРѕСЃРѕР±РЅРѕС‚ей
 flow[100][100],  // РњР°С‚рица РїРѕС‚РѕРєР°
 color[100],      // Р¦РІРµС‚Р° РґР»СЏ РІРµСЂС€РёРЅ
 pred[100];       // РњР°СЃСЃРёРІ РїСѓС‚Рё
 int head, tail;  // РќР°С‡Р°Р»Рѕ, РљРѕРЅРµС†
 int q[102];      // РћС‡РµСЂРµРґСЊ, С…ранящая РЅРѕРјРµСЂР° РІРµСЂС€РёРЅ РІС…одящих РІ РЅРµС‘
//Сравнение РґРІСѓС… С†РµР»С‹С… Р·РЅР°С‡РµРЅРёР№
int min(int x, int y)
{
  if (x < y)
    return x;
  else
    return y;
}
//Добавить РІ РѕС‡РµСЂРµРґСЊ (РјС‹ СЃС‚упили РЅР° РІРµСЂС€РёРЅСѓ)
void enque(int x)
{
  q[tail] = x;     // Р·Р°РїРёСЃР°С‚СЊ С… РІ С…РІРѕСЃС‚
  tail++;          // С…востом СЃС‚ановиться СЃР»РµРґСѓСЋС‰РёР№ СЌР»РµРјРµРЅС‚
  color[x] = GREY; // Р¦РІРµС‚ СЃРµСЂС‹Р№ (РёР· Р°Р»РіРѕСЂРёС‚РјР° РїРѕРёСЃРєР°)
}
//Убрать РёР· РѕС‡РµСЂРµРґРё (Вершина С‡С‘рная, РЅР° РЅРµС‘ РЅРµ С…одить)
int deque()
{
  int x = q[head];  // Р—аписать РІ С… Р·РЅР°С‡РµРЅРёРµ РіРѕР»РѕРІС‹
  head++;           // РЎРѕРѕС‚ветственно РЅРѕРјРµСЂ РЅР°С‡Р°Р»Р° РѕС‡РµСЂРµРґРё СѓРІРµР»РёС‡РёРІР°РµС‚СЃСЏ
  color[x] = BLACK; // Р’ершина С… - РѕС‚мечается РєР°Рє РїСЂРѕС‡РёС‚анная
  return x;         // Р’озвращается РЅРѕРјРµСЂ С… РїСЂРѕС‡РёС‚анной РІРµСЂС€РёРЅС‹
}
//РџРѕРёСЃРє РІ С€РёСЂРёРЅСѓ
int bfs(int start, int end)
{
  int u,v;
  for( u = 0; u < n; u++ ) // РЎРЅР°С‡Р°Р»Р° РѕС‚мечаем РІСЃРµ РІРµСЂС€РёРЅС‹ РЅРµ РїСЂРѕР№РґРµРЅРЅС‹РјРё
    color[u]=WHITE;   
 
  head=0;   // РќР°С‡Р°Р»Рѕ РѕС‡РµСЂРµРґРё 0
  tail=0;   // РҐРІРѕСЃС‚ 0
  enque(start);      // Р’ступили РЅР° РїРµСЂРІСѓСЋ РІРµСЂС€РёРЅСѓ
  pred[start]= -1;   // РЎРїРµС†РёР°Р»СЊРЅР°СЏ РјРµС‚РєР° РґР»СЏ РЅР°С‡Р°Р»Р° РїСѓС‚Рё
  while(head!=tail)  // РџРѕРєР° С…РІРѕСЃС‚ РЅРµ СЃРѕРІРїР°РґС‘С‚ СЃ РіРѕР»РѕРІРѕР№
  {
    u=deque();       // РІРµСЂС€РёРЅР° u РїСЂРѕР№РґРµРЅР°
    for( v = 0; v < n; v++ ) // РЎРјРѕС‚СЂРёРј СЃРјРµР¶РЅС‹Рµ РІРµСЂС€РёРЅС‹
    {
     // Р•СЃР»Рё РЅРµ РїСЂРѕР№РґРµРЅР° Рё РЅРµ Р·Р°РїРѕР»РЅРµРЅР°
     if(color[v] == WHITE && (capacity[u][v]-flow[u][v]) > 0) {
       enque(v);  // Р’ступаем РЅР° РІРµСЂС€РёРЅСѓ v
       pred[v]=u; // РџСѓС‚СЊ РѕР±РЅРѕРІР»СЏРµРј
     }
    }
  }  
  if(color[end] == BLACK) // Р•СЃР»Рё РєРѕРЅРµС‡РЅР°СЏ РІРµСЂС€РёРЅР°, РґРѕС€Р»Рё - РІРѕР·РІСЂР°С‰Р°РµРј 0
    return 0;
  else return 1;
}
//Максимальный РїРѕС‚РѕРє РёР· РёСЃС‚РѕРєР° РІ СЃС‚РѕРє
int max_flow(int source, int stock)
{
  int i,j,u;
  int maxflow=0;            // Р˜Р·РЅР°С‡Р°Р»СЊРЅРѕ РЅСѓР»РµРІРѕР№
  for( i = 0; i < n; i++ )  // Р—ануляем РјР°С‚рицу РїРѕС‚РѕРєР°
    {
      for( j = 0; j < n; j++)
      flow[i][j]=0;
    }
  while(bfs(source,stock) == 0)             // РџРѕРєР° СЃРµС‰РµСЃС‚вует РїСѓС‚СЊ
    {
      int delta=10000;
      for(u = n-1; pred[u] >= 0; u=pred[u]) // РќР°Р№С‚Рё РјРёРЅРёРјР°Р»СЊРЅС‹Р№ РїРѕС‚РѕРє РІ СЃРµС‚Рё
      {
        delta=min(delta, ( capacity[pred[u]][u] - flow[pred[u]][u] ) );
      }
      for(u = n-1; pred[u] >= 0; u=pred[u]) // РџРѕ Р°Р»РіРѕСЂРёС‚РјСѓ Р¤РѕСЂРґР°-Фалкерсона 
      {     
        flow[pred[u]][u] += delta;
        flow[u][pred[u]] -= delta;
      }
      maxflow+=delta;                       // РџРѕРІС‹С€Р°РµРј РјР°РєСЃРёРјР°Р»СЊРЅС‹Р№ РїРѕС‚РѕРє
    }
  return maxflow;
}
//Описав РІСЃРµ СЌС‚Рё РїСЂРµРґРІР°СЂРёС‚ельные С„ункции, РјРѕР¶РµРј РєСЂР°С‚РєРѕ РѕС„ормить С„ункцию main().
int main()
{
  cin >> n;
  cout << "Количество РІРµСЂС€РёРЅ: " << n << endl;  
  int i,j;
  for( i = 0; i < n; i++ )
    {
      for( j = 0; j < n; j++ )
        cin >> capacity[i][j];
    }
 
  cout << "Максимальный РїРѕС‚РѕРє: " << max_flow(0,n-1) << endl;
  cout << "Матрица С‡РµРіРѕ-то С‚ам: " << endl;
    for( i = 0; i < n; i++ ) 
    {
      for( j = 0; j < n; j++ )
        cout << flow[i][j] << " ";
      cout << endl;
    }
 
  getch();
  return 0;
}
          
          
Comments: