题目链接：USACO - Controlling Companies
对每个结点进行一次bfs。bfs时，当且仅当被起始点控制的点入队。然后最后可以得到所有被控制的点。
/* ID: xdujlx1 PROG: concom LANG: C++ */ #include<bits/stdc++.h> using namespace std; int d[107]; int G[107][107]; bool vis[107]; vector<int> adj[107]; vector<pair<int,int> > ans; void ioinit() { freopen("concom.in","r",stdin); freopen("concom.out","w",stdout); } void bfs(int u) { int st=u; memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); queue<int> q; for(int i=0;i<adj[u].size();i++) { int v=adj[u][i]; d[v]+=G[u][v]; if(d[v]>50) q.push(v),vis[v]=true; } while(!q.empty()) { u=q.front();q.pop(); for(int i=0;i<adj[u].size();i++) { int v=adj[u][i]; d[v]+=G[u][v]; if(!vis[v]&&d[v]>50) q.push(v),vis[v]=true; } } for(int i=1;i<=100;i++) if(vis[i]&&i!=st) ans.push_back(make_pair(st,i)); } int main() { ioinit(); int n,u,v,c; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&u,&v,&c); G[u][v]=c; adj[u].push_back(v); } for(int i=1;i<=100;i++) bfs(i); sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) { printf("%d %d\n",ans[i].first,ans[i].second); } return 0; }