Home > Old Blog Posts > USACO 2.3.5 Controlling Companies

USACO 2.3.5 Controlling Companies


可以看出,一条关系链的长度不会超过100,所以我们可以搜索100次,每次判断两两之间是否有控制关系,总复杂度为O(n^2)(实际上应该是O(n^3))

另外还有O(n^2)的算法,但上述的方法比较容易实现,且对付这道题的数据已经足够了。

代码:

/*
ID: dementr1
PROG: concom
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“concom.in”);
ofstream fout(“concom.out”);
int N,money[101][101];
bool control[101][101],exist[101];
void init()
{
int i,a,b;
memset(control,false,sizeof(control));
memset(exist,false,sizeof(exist));
memset(money,0,sizeof(money));
fin>>N;
for(i=0;i<N;i++)
{
fin>>a>>b;
fin>>money[a][b];
if(money[a][b]>=50) control[a][b]=true;
exist[a]=true;
exist[b]=true;
}
for(i=1;i<=100;i++) control[i][i]=true;
}
void work()
{
int i,j,k,time;
for(time=1;time<=100;time++)
{
for(i=1;i<=100;i++)
{
if(!exist[i]) continue;
for(j=1;j<=100;j++)
{
if(!exist[j]) continue;
if(control[i][j]) continue;
int tmp=0;
for(k=1;k<=100;k++)
{
if(!exist[k]) continue;
if(control[i][k]) tmp+=money[k][j];
}
if(tmp>=50) control[i][j]=true;
}
}
}
for(i=1;i<=100;i++)
{
if(!exist[i]) continue;
for(j=1;j<=100;j++)
{
if(!exist[j]) continue;
if(i!=j&&control[i][j]) fout<<i<<” “<<j<<endl;
}
}
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: