记录编号	51758	评测结果	AAAAAAAAA
题目名称	[USACO 2.3.5]控制公司	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2012-12-30 16:40:25	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n=0;
int con[101][101]={0};
void input(void){
	int m;
	scanf("%d",&m);
	int i,j,k,p;
	for(k=0;k<m;k++){
		scanf("%d%d%d",&i,&j,&p);
		if(i>n) n=i;
		if(j>n) n=j;//不给公司数这是要作死......
		con[i-1][j-1]=p;
	}
}
void sicon(int x){//计算公司x的情况
	bool under[101]={0};//under control......
	int nowcon[101]={0};//现在直接/间接控制其他公司的股份
	int i,j,sum=0;
	for(i=0;i<n;i++) nowcon[i]=con[x][i];//A控制B,B间接控制C,则A不一定控制C,所以con不能受影响
	under[x]=1;
	bool flag;
	do{
		flag=false;
		for(i=0;i<n;i++){
			if(under[i]) continue;
			if(nowcon[i]>50){
				flag=true;
				under[i]=1;
				sum++;
				for(j=0;j<n;j++){
					if(under[j]) continue;
					nowcon[j]+=con[i][j];
				}//有点类似于'松弛'的思想
			}
		}
	}while(flag);
	if(sum){
		for(i=0;i<n;i++){
			if(i==x) continue;
			if(under[i]) printf("%d %d\n",x+1,i+1);
		}
	}
}
int main(){
	freopen("concom.in","r",stdin);
	freopen("concom.out","w",stdout);
	input();
	for(int i=0;i<n;i++) sicon(i);
	return 0;
}