USACO:Controlling Companies
1253 ワード
/*
ID: Jang Lawrence
PROG: concom
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define mp make_pair
using namespace std;
typedef long long lng;
typedef pair<int, int> pii;
int n;
bool is[110][110];
int have[110][110];
int now[110][110];
void checkmax(int &x,int y){if(x<y) x=y;}
int main()
{
#ifndef DEBUG
freopen("concom.in","r",stdin);
freopen("concom.out","w",stdout);
#endif
int m;
scanf("%d",&m);
n=0;
queue<pii> q;
for(int i=1;i<=m;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
have[u][v]=w;now[u][v]=w;
if(w>50) {is[u][v]=1;q.push(mp(u,v));}
checkmax(n,u);checkmax(n,v);
}
while(!q.empty())
{
pii U=q.front();
q.pop();
int u=U.first,v=U.second;
for(int i=1;i<=n;++i)
if(i!=v&&i!=u&&!is[u][i])
{
now[u][i]+=have[v][i];
if(now[u][i]>50)
{
is[u][i]=1;
q.push(mp(u,i));
}
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(is[i][j]&&i!=j)
printf("%d %d
",i,j);
return 0;
}