计算机网络 - STP 生成树协议
生成树协议
一个简单实现,单线程事件驱动模拟。
#include <cstdio>
#include <algorithm>
#include <set>
#include <list>
#include <string>
using namespace std;
const int MAX_VALUE = 2147483647;
struct BPDU {
int rid;
int cost;
int sid;
int port;
friend bool operator < (BPDU a, BPDU b) {
if(a.rid != b.rid) return a.rid < b.rid;
if(a.cost != b.cost) return a.cost < b.cost;
if(a.sid != b.sid) return a.sid < b.sid;
if(a.port != b.port) return a.port < b.port;
return true;
}
};
list<pair<BPDU, int> > events;
set<int> net[201];
struct NetFlag {
bool dp = true;
} netFlag[201];
struct Bridge {
int id;
int link[16];
int cost[16];
BPDU minBPDU;
void receive(BPDU bpdu, int from) {
int minValue = MAX_VALUE;
for(int i=0; i<16; i++) {
if(link[i] == from) {
minValue = min(minValue, cost[i]);
}
}
bpdu.cost += minValue;
if(minBPDU < bpdu) return;
minBPDU = bpdu;
for(int i=0; i<16; i++) {
if(link[i] == 0) continue;
events.push_back(make_pair(BPDU{minBPDU.rid, minBPDU.cost, id, i}, link[i]));
}
}
} bridge[201];
void spaningTree() {
for(int i=1; i<=200; i++) {
for(int j=0; j<16; j++) {
int linkNet = bridge[i].link[j];
if(linkNet != 0) {
events.push_back(make_pair(BPDU{i, 0, i, j}, linkNet));
}
}
}
while(events.size() != 0) {
BPDU bpdu = events.front().first;
int target = events.front().second;
events.pop_front();
for(auto it=net[target].begin(); it!=net[target].end(); it++) {
bridge[*it].receive(bpdu, target);
}
}
}
void link(int b, int p, int l, int c) {
bridge[b].link[p] = l;
bridge[b].cost[p] = c;
net[l].insert(b);
}
string role[201][16];
int main() {
for(int i=1; i<=200; i++) {
bridge[i].id = i;
bridge[i].minBPDU = BPDU{i, 0, i, 0};
}
freopen("1.in", "r", stdin);
int m; scanf("%d", &m);
for(int i=1; i<=m; i++) {
char opt[1024];
scanf("%s", opt);
int b, p, l, c;
scanf("%d%d%d%d", &b, &p, &l, &c);
link(b, p , l, c);
}
spaningTree();
for(int i=1; i<=200; i++) {
for(int j=0; j<16; j++) {
role[i][j] = "BP";
}
}
for(int i=1; i<=200; i++) {
int rid = bridge[i].minBPDU.rid;
int sid = bridge[i].minBPDU.sid;
int port = bridge[i].minBPDU.port;
int cost = bridge[i].minBPDU.cost;
int toNet = bridge[sid].link[port];
if(i != rid) {
int minCost = MAX_VALUE, rp;
for(int j=0; j<16; j++) {
int linkNet = bridge[i].link[j];
int linkCost = bridge[i].cost[j];
if(linkNet == 0) continue;
if(linkNet == toNet && linkCost < minCost) {
minCost = linkCost;
rp = j;
}
}
role[i][rp] = "RP";
}
}
for(int i=1; i<=200; i++) {
if(net[i].size() == 0) continue;
int minCost = MAX_VALUE, db, dp;
for(auto it=net[i].begin(); it!=net[i].end(); it++) {
int tb = *it;
if(bridge[tb].minBPDU.cost < minCost) {
minCost = bridge[tb].minBPDU.cost;
db = tb;
}
}
minCost = MAX_VALUE;
for(int j=0; j<16; j++) {
int linkNet = bridge[db].link[j];
int linkCost = bridge[db].cost[j];
if(linkNet == i && linkCost < minCost) {
minCost = linkCost;
dp = j;
}
}
role[db][dp] = "DP";
}
for(int i=1; i<=200; i++) {
for(int j=0; j<16; j++) {
int linkNet = bridge[i].link[j];
if(linkNet == 0) continue;
printf("%d %d %d %s\n", i, j, linkNet, role[i][j].c_str());
}
}
}