#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;

//隣接行列がgraphであるようなグラフにおいて、startからgoalまで幅優先探索を行う。
//goalまでたどりつけばtrue、たどりつけなければfalseを返す。
//trueが返るときには、prevに「直前の頂点」の情報が入っている。
bool bfs(const vector<vector<int> > &graph, int start, int goal, vector<int> &prev)
{
  const int n = graph.size(); //n:グラフの頂点数

  //「直前の頂点」の情報をクリア
  for(int i = 0; i < n; ++i){
    prev[i] = -1;
  }
  //アルゴリズムの都合上、出発点の「直前」は出発点自身とする:
  prev[start] = start;

  //「まだたどってない頂点」をキューで管理する。最初は出発点だけ。
  deque<int> frontier;
  frontier.push_back(start);

  //キューに頂点が残っていたらループ
  while(! frontier.empty()){
    int vertex = frontier[0];
    frontier.pop_front();

    //目的地に到達していれば終わり
    if(vertex == goal){
      return true;
    }

    //「次にたどるべき頂点」をキューに追加する
    for(int next = 0; next < n; ++next){
      //はじめて見る頂点で今の頂点から行けるものをキューに追加
      if(prev[next] == -1 && graph[vertex][next] > 0){
    prev[next] = vertex;
    frontier.push_back(next);
      }
    }
  }

  //目的地にたどりつかなかったのでfalse.
  return false;
}

//辺(i,j)の容量がgraph[i][j]であるようなグラフにおけるsourceからsinkへの最大フローを求める。
//求めた最大フローはflowに入る。
//最大フローの値を返す。
int maxFlow(vector<vector<int> > graph, int source, int sink, vector<vector<int> > &flow)
{
  const int n = graph.size(); //n:グラフの頂点数

  //フローflowと値valueを初期化
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      flow[i][j] = 0;
    }
  }
  int value = 0;

  //幅優先探索の準備
  vector<int> prev(n);

  //経路が見付かる限りフローを更新
  while(bfs(graph,source,sink,prev)){
    //prevに従って,見付けた経路の容量の最小値を求める.
    int capacity = graph[prev[sink]][sink];

    for(int v = sink; v != source; v = prev[v]){
      if(capacity > graph[prev[v]][v]){
    capacity = graph[prev[v]][v];
      }
    }

    //フローと残余ネットワークを更新
    for(int v = sink; v != source; v = prev[v]){
      int pv = prev[v];
      flow[pv][v] += capacity;
      graph[pv][v] -= capacity;
      graph[v][pv] += capacity;
    }
    value += capacity;
  }

  return value;
}

double exprand(double average)
{
  double r = rand() / (RAND_MAX + 1.0);
  return -log(1-r) * average;
}

struct Packet {
  int source; //入力ポート
  int dest; //出力ポート
  int arriveTime; //ハブへの到着時刻
  int deliverTime; //ハブからの排出時刻
};

typedef deque<Packet> PacketQueue;

//ハブに届いたパケットを生成する.
Packet makePacket(int in_port, int current, int ports)
{
  Packet packet;

  packet.source = in_port;
  packet.dest = int(rand() / (RAND_MAX + 1.0) * (ports-1));
  if(packet.dest >= packet.source){
    ++packet.dest;
  }
  packet.arriveTime = current;
  packet.deliverTime = -1;

  return packet;
}

//ポート数Ports,スイッチ転送量xppcパケット/クロックのハブのシミュレーションを行う.
//パケットの平均到着時間間隔はTa,シミュレーション時間はdurationとする.
void runSimulation(int Ports, int xppc, double Ta, int duration)
{
  //入力バッファは入力ポートごとかつ出力ポートごと
  vector<vector<PacketQueue> > inputBuffer(Ports, vector<PacketQueue>(Ports));

  //次に各入力ポートにパケットがくるタイミング
  vector<int> nextPacketTime(Ports);

  //最初のパケットのタイミングを設定して....
  for(int in_port = 0; in_port < Ports; ++in_port){
    nextPacketTime[in_port] = int(exprand(Ta));
  }

  //シミュレーション開始
  printf("Simulation start\n");
  for(int current = 0; current < duration; ++current){
    //まず入力パケットをもらう
    for(int in_port = 0; in_port < Ports; ++in_port){
      while(current == nextPacketTime[in_port]){
    Packet packet = makePacket(in_port, current, Ports);
    inputBuffer[in_port][packet.dest].push_back(packet);
    nextPacketTime[in_port] += int(exprand(Ta));
      }
    }

    //グラフを作って
    const int Vertices = 2*Ports+2;
    const int Source = 2*Ports;
    const int Sink = 2*Ports+1;
    vector<vector<int> > graph(Vertices, vector<int>(Vertices));
    for(int in_port = 0; in_port < Ports; ++in_port){
      for(int out_port = 0; out_port < Ports; ++out_port){
    graph[in_port][Ports+out_port] = inputBuffer[in_port][out_port].size();
      }
    }
    for(int in_port = 0; in_port < Ports; ++in_port){
      graph[Source][in_port] = xppc;
    }
    for(int out_port = 0; out_port < Ports; ++out_port){
      graph[Ports+out_port][Sink] = xppc;
    }

    //最大フローを求め
    vector<vector<int> > flow(Vertices, vector<int>(Vertices));
    maxFlow(graph, Source, Sink, flow);

    //それに従ってパケットを送り出す
    for(int in_port = 0; in_port < Ports; ++in_port){
      for(int out_port = 0; out_port < Ports; ++out_port){
    for(int p = 0; p < flow[in_port][Ports+out_port]; ++p){
      inputBuffer[in_port][out_port][0].deliverTime = current;
      inputBuffer[in_port][out_port].pop_front();
    }
      }
    }
  }

  //時間がきたのでシミュレーション終了
  printf("Simulation finished\n");
}

//テスト用のmain
int main()
{
  const int Ports = 4; //ポート数

  const double Ta = 2; //平均到着時間間隔
  const int T = 1000; //シミュレートする時間数
  const int P = 1; //1ポートあたり転送パケット数

  srand(time(NULL));
  runSimulation(Ports, P, Ta, T);
  return 0;
}