/*
http://t...content-available-to-author-only...h.net/test/read.cgi/tech/1339338438/639

課題　ハブのシミュレーション
ここではVirtual Output Queuing構成のハブをシミュレーションする。
設定は以下のようにする:
●ポート数は4
●パケットの入出力やスイッチにおけるパケット転送はクロック単位で同期している。
●入力ポートからスイッチへの、またスイッチから出力ポートへの転送は1クロックにつきPパケット。
●各入力ポートでは、パケットが平均時間間隔がTaの指数分布に従って到着する。
●各パケットの宛先ポートは、"入力ポートに対応する出力ポート以外のポート"から等確率でランダムに選ぶ。
　つまり、"入力ポート1からやってきたパケット"の宛先は、出力ポート0,2,3のいずれかから等確率で選ばれる。
　（これは"全てのポートが対称である"ことを意味する。）
●Tクロックの間動作をさせる。

Ta=2,T=1000,P=1として実行し、全てのパケットに対する転送遅延
（入力ポートに入ってから出力ポートに出ていくまでの時間）の
最大値と平均値を求めよ。
http://i...content-available-to-author-only...e.com/T3e0j を参考にしてプログラムを作成してもかまわない。
ただし、このプログラムは何も表示しないので各クロックごとに
どの入力ポートからパケットが到着したのか、あるいはどれだけのパケットを
転送したのかなどを表示させるとわかりやすいだろう。
もちろん、必要な情報を収集することも忘れないこと。

回答者注釈：
・インデントを直した
・追加した部分に関しては行頭にマークを付けた
・毎回実行結果が異なる
・if (0) の部分を if (1) にすると、振る舞いが表示される
*/

#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));
    }
 
    //シミュレーション開始
/**/int max =0, sum = 0, count = 0; // 情報収集用変数
    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;
/**/                // 情報収集ここから
/**/                Packet& x = inputBuffer[in_port][out_port][0]; // too long
/**/                int delay = x.deliverTime - x.arriveTime;
/**/                if (0) { // パケット到着時の情報表示
/**/                    printf("src:%d dst:%d arr:%d del:%d delay:%d\n",
/**/                           x.source, x.dest, x.arriveTime, x.deliverTime,
/**/                           delay);
/**/                }
/**/                if (delay > max)
/**/                    max = delay;
/**/                sum += delay;
/**/                ++count;
/**/                // 情報収集ここまで
                    inputBuffer[in_port][out_port].pop_front();
                }
            }
        }
    }
    //時間がきたのでシミュレーション終了
    printf("Simulation finished\n");
/**/// 設題の情報を表示
/**/printf("max: %d\n", max);
/**/printf("average: %f\n", (double) sum / count);
}
 
//テスト用の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;
}