现在的位置: 首页 > 综合 > 正文

USACO:Controlling Companies

2013年04月05日 ⁄ 综合 ⁄ 共 838字 ⁄ 字号 评论关闭
/*
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\n",i,j);
    return 0;
}

抱歉!评论已关闭.