直接bfs,模拟一下就好了,难度不大,要注意节点插入顺序。
#include<bits/stdc++.h>
using namespace std;
const int N=350;
typedef struct Flow{
int port;
int fl;
}Flow;
vector<Flow> flow;
int cur=0;
int h[N],e[N],ne[N];
bool st[N];
int id;
int n;
void add(int a,int b)
{
e[id]=b;
ne[id]=h[a];
h[a]=id++;
}
bool cmp(Flow a,Flow b)
{
if(a.fl!=b.fl) return a.fl>b.fl;
else return a.port<b.port;
}
void bfs()
{
queue<int> q;
q.push(100);
st[100]=true;
while(q.size())
{
int t=q.front();
q.pop();
vector<int> tmp;
for(int i=h[t];i!=-1;i=ne[i]) tmp.push_back(i);
for(int i=tmp.size()-1;i>=0;i--)
{
int j=e[tmp[i]];
if(!st[j])
{
if(j<100)
{
cout<<flow[cur++].port<<" "<<j;
puts("");
}
st[j]=true;
q.push(j);
}
}
}
}
int main()
{
memset(h,-1,sizeof(h));
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b!=-1)
add(a,b);
if(c!=-1)
add(a,c);
if(d!=-1)
add(a,d);
}
int port;
while(cin>>port)
{
int fl;
cin>>fl;
Flow tmp;
tmp.fl=fl;
tmp.port=port;
flow.push_back(tmp);
}
sort(flow.begin(),flow.end(),cmp);
bfs();
return 0;
}
```