concom.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: concom
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("concom.in");
ofstream out("concom.out");
#define MAX(A,B) (A>B?A:B)
int control[101][101]={0};
int N=0;
bool hash[101];

int main()
{
	int n,t1,t2,t3;bool tcount;
	in>>n;
	for(int a=1;a<=n;a++)
	{
		in>>t1>>t2>>t3;
		N=MAX(t1,N);
		N=MAX(t2,N);
		control[t1][t2]=t3;
	}
	for(int a=1;a<=N;a++)
	{
		memset(hash,0,sizeof(hash));
		while(true)
		{
			tcount=false;
			for(int b=1;b<=N;b++)
			{
				if(!hash[b]&&control[a][b]>50)
				{
					hash[b]=true;
					tcount=true;
					for(int c=1;c<=N;c++)
					{
						control[a][c]+=control[b][c];
						if(control[a][c]>100)
							control[a][c]=100;
					}
				}
			}
			if(!tcount)
				break;
		}
	}
	for(int a=1;a<=N;a++)
		for(int b=1;b<=N;b++)
			if(control[a][b]>50&&a!=b)
				out<<a<<" "<<b<<endl;
	return 0;
}