Controlling Companies
DESCRIPTION
Some companies are partial owners of other companies because they have acquired part of their total shares of stock. For example, Ford at one point owned 12% of Mazda. It is said that a company A controls company B if at least one of the following conditions is satisfied:
Company A = Company B
Company A owns more than 50% of Company B
Company A controls K (K >= 1) companies denoted C1, ..., CK with each company Ci owning xi% of company B and x1 + .... + xK > 50%.
Given a list of triples (i,j,p) which denote company i owning p% of company j, calculate all the pairs (h,s) in which company h controls company s. There are at most 100 companies.
Write a program to read the list of triples (i,j,p) where i, j and p are positive integers all in the range (1..100) and find all the pairs (h,s) so that company h controls company s.
PROGRAM NAME: concom
Line 1:
n, the number of input triples to follow
Line 2..n+1:
Three integers per line as a triple (i,j,p) described above.
3
1 2 80
2 3 80
3 1 20
List 0 or more companies that control other companies. Each line contains two integers that denote that the company whose number is the first integer controls the company whose number is the second integer. Order the lines in ascending order of the first integer (and ascending order of the second integer to break ties). Do not print that a company controls itself.
SAMPLE OUTPUT (file concom.out)
1 2
1 3
2 3
THOUGHTS:
第一反应Dfs？其实也可以Bfs。 我们首先注意到输入的部分，每个公司的编号不是连续的。（样例只是一个巧合）为了方便操作，博主做的第一件事是将它们进行哈希（Hash），具体方式就是进行排序，然后让每个编号与他们的次序进行一一映射。这样Bfs的过程中便不需要考虑编号问题，最后输出时按照Hash的数组输出符合要求的即可。 然后我们注意到它的规则，是通过加和的方式寻找所有的“父亲”关系。也就是说每当出现一对新关系时，便需要更新该关系中父亲对所有结点（准确的说是它孩子掌握的节点）的股份，每当出现新的父子关系时将这对节点入队。循环往复，直到队列为空为止。操作起来很简单。 最后遍历所有关系，将股份>50的所有对数按照按照原本的编号即可（由于Hash时就是从小到大排序，因此一定是字典序输出）。
DIFFICULTIES: pj
AC PROGRAM: （此次有注释）
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (register int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define ROF(i, a, b) for (register int i = (a), i##_end_ = (b); i > i##_end_; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG debug("Passing [%s] in LINE %d\n",__FUNCTION__, __LINE__)
const char Fin[] =
"concom.in";
const char Fout[] =
"concom.out";
void In()
{
freopen(Fin,
"r", stdin);
freopen(Fout,
"w", stdout);
return ;
}
int GetInt()
{
register int x;
scanf(
"%d", &x);
return x;
}
const int MAXN =
2550;
const int MAXM =
105;
typedef pair<
int,
int> pii;
#define x first
#define y second
#define m_p(a, b) make_pair(a, b)
int n;
int F[MAXM][MAXM];
queue<pii> Q;
int A[MAXM];
void ReadFile()
{
int X[MAXN][
3], m;
map<int, int> M;
FOR(i,
0, m = GetInt())
{
FOR(j,
0,
3)
X[i][j] = GetInt();
M[X[i][
0]] =
1;
M[X[i][
1]] =
1;
}
n = M.size();
int i =
0;
for(
map<int, int>::iterator iter = M.begin(); iter != M.end(); ++iter, ++i)
{
M[iter->first] = i;
A[i] = iter->first;
}
FOR(i,
0, m)
{
F[M[X[i][
0]]][M[X[i][
1]]] = X[i][
2];
if(X[i][
2] >
50)
Q.push(m_p(M[X[i][
0]], M[X[i][
1]]));
}
return ;
}
void Bfs()
{
while(!Q.empty())
{
pii& cur = Q.front();
FOR(i,
0, n)
{
if(F[cur.x][i] >
50)
continue;
F[cur.x][i] += F[cur.y][i];
if(F[cur.x][i] >
50)
Q.push(m_p(cur.x, i));
}
Q.pop();
}
return ;
}
void Print()
{
FOR(i,
0, n)
FOR(j,
0, n)
if(F[i][j] >
50 && i != j)
printf(
"%d %d\n", A[i], A[j]);
return ;
}
int main()
{
In();
ReadFile();
Bfs();
Print();
return 0;
}
P.S:
跑的确实很快，比Dfs的快到不知哪里去了…当然估计是因为他们没写好。。
Skq_Liao 2017/07/11 21:44 于家中
