controllingcompanies - codetrick
Some companies are partial owners of other companies because they have acquired part of their total shares of stock. For example, Ford owns 12% of Mazda. It is said that a company A controls company B if at least one of the following conditions is satisfied:
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.
这道题目解法如下， 首先扫描输入， 记录所有公司之间的控制情况。然后遍历每一个公司 （eg:A公司），将该公司直接控制的公司加入链表（eg:B1、B2、B3公司）。然后BFS链表中的所有控制的公司，更新A公司对其他公司的控股（参考条件3），如果大于50%则加入链表中，直到链表中再没有元素。
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-controlling-companies/
http://qingtangpaomian.iteye.com/blog/1635802
Read full article from controllingcompanies - codetrick
Some companies are partial owners of other companies because they have acquired part of their total shares of stock. For example, Ford owns 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%.
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
INPUT FORMAT
| 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. |
SAMPLE INPUT (file concom.in)
3 1 2 80 2 3 80 3 1 20
OUTPUT FORMAT
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 3http://lujunda.cn/2013/01/01/usacosection-2-3%E6%90%9C%E7%B4%A2-controlling-companies/
有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。例如，福特公司拥有马自达公司12%的股票。据说，如果至少满足了以下三个条件之一，公司A就可以控制公司B了：
- 公司A = 公司B。
- 公司A拥有大于50%的公司B的股票。
- 公司A控制K(K >= 1)个公司，记为C1, …, CK，每个公司Ci拥有xi%的公司B的股票，并且x1+ …. + xK > 50%。
给你一个表，每行包括三个数(i,j,p)；表明公司i享有公司j的p%的股票。计算所有的数对(h,s)，表明公司h控制公司s。至多有100个公司。写一个程序读入N组数(i,j,p)，i,j和p是都在范围(1..100)的正整数，并且找出所有的数对(h,s)，使得公司h控制公司s。
http://qingtangpaomian.iteye.com/blog/1635802这道题目解法如下， 首先扫描输入， 记录所有公司之间的控制情况。然后遍历每一个公司 （eg:A公司），将该公司直接控制的公司加入链表（eg:B1、B2、B3公司）。然后BFS链表中的所有控制的公司，更新A公司对其他公司的控股（参考条件3），如果大于50%则加入链表中，直到链表中再没有元素。
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-controlling-companies/
int owns[NCOM][NCOM]; /* [i,j]: how much of j do i and its controlled companies own? */int controls[NCOM][NCOM]; /* [i, j]: does i control j? *//* update info: now i controls j */voidaddcontroller(int i, int j){ int k; if(controls[i][j]) /* already knew that */ return; controls[i][j] = 1; /* now that i controls j, add to i's holdings everything from j */ for(k=0; k<NCOM; k++) owns[i][k] += owns[j][k]; /* record the fact that controllers of i now control j */ for(k=0; k<NCOM; k++) if(controls[k][i]) addcontroller(k, j); /* if i now controls more companies, record that fact */ for(k=0; k<NCOM; k++) if(owns[i][k] > 50) addcontroller(i, k);}/* update info: i owns p% of j */voidaddowner(int i, int j, int p){ int k; /* add p% of j to each controller of i */ for(k=0; k<NCOM; k++) if(controls[k][i]) owns[k][j] += p; /* look for new controllers of j */ for(k=0; k<NCOM; k++) if(owns[k][j] > 50) addcontroller(k, j);}voidmain(void){ FILE *fin, *fout; int i, j, n, a, b, p; fin = fopen("concom.in", "r"); fout = fopen("concom.out", "w"); assert(fin != NULL && fout != NULL); for(i=0; i<NCOM; i++) controls[i][i] = 1; fscanf(fin, "%d", &n); for(i=0; i<n; i++) { fscanf(fin, "%d %d %d", &a, &b, &p); addowner(a, b, p); } for(i=0; i<NCOM; i++) for(j=0; j<NCOM; j++) if(i != j && controls[i][j]) fprintf(fout, "%d %d\n", i, j); exit(0);}http://qingtangpaomian.iteye.com/blog/1635802
Read full article from controllingcompanies - codetrick
