Created
June 19, 2018 05:27
-
-
Save jwon0615/9336ab0a860927a79e75abb48a18d164 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//파급효과 | |
// | |
//기업의 수 n이 주어지고 자본이 이동하는 간선 m이 주어진다 | |
//n+1줄까지 자본의 크기(long long int)가 주어진다 | |
//이후 m줄 동안 a번째 기업이 b번째 기업에 투자하는 비율c가 주어진다. | |
//마지막 줄엔 하나의 기업을 선택한다 | |
//한 기업을 선택했을때,이 기업으로부터 야기된 유동자본의 규모를 계산하시오. | |
// | |
//http://mydb.tistory.com/222 (순환출자 예시-롯데) | |
#include <stdio.h> | |
typedef long long int lint; | |
lint total_cap; | |
lint cap[100]; | |
float invest[100][100]; | |
bool chk[100][100]; | |
int n,m,k; | |
long long int sum; | |
void set(int v,float f){ | |
for(int i=0; i<n; i++) | |
if(chk[v][i]) return; //이미 방문한 간선이면 리턴 | |
for(int i=0; i<n; i++){ | |
if(invest[v][i]&&!chk[v][i]) //간선이 존재하고 방문하지 않은 간선 | |
{ | |
chk[v][i]=1; | |
sum+=(lint)cap[i]*invest[v][i]*f; //지분율 * 대상 기업 자본금 | |
sum=(lint)(sum/1000)*1000; //1000원 미만은 버림 | |
set(i,f*invest[v][i]); | |
} | |
} | |
} | |
int main(){ | |
scanf("%d %d", &n, &m); | |
for(int i=0; i<n; i++){ | |
scanf(" %lld", cap+i); | |
total_cap+=cap[i]; | |
} | |
for(int i=0; i<m; i++){ | |
int a, b; | |
float temp; | |
scanf("%d %d %f", &a, &b, &temp);//a가 가진 b의 지분 temp | |
invest[a][b]=temp; | |
} | |
scanf("%d", &k); | |
set(k, 1); //탐색시작 | |
printf("\n\n%lld\n%lld", sum,total_cap); | |
} | |
//test case 0 | |
//1 0 | |
//100000 | |
//test case 1 | |
//3 3 | |
//1000000 | |
//2000000 | |
//3000000 | |
//0 1 0.5 | |
//1 2 0.5 | |
//2 0 0.5 | |
//test case 2 | |
//5 9 | |
//100000000 | |
//200000000 | |
//100000000 | |
//300000000 | |
//400000000 | |
//0 1 0.2 | |
//1 2 0.35 | |
//1 3 0.15 | |
//2 0 0.45 | |
//2 3 0.20 | |
//3 4 0.30 | |
//4 1 0.30 | |
//4 2 0.05 | |
//4 0 0.80 | |
//test case 3 | |
//4 6 | |
//21918280000 | |
//31415230000 | |
//65378920000 | |
//54329420000 | |
//0 1 0.2 | |
//0 2 0.8 | |
//0 3 1 | |
//1 2 0.4 | |
//1 3 0.015 | |
//2 3 0.5 | |
//test case 4 | |
// | |
//12 40 | |
//832600000000 | |
//316000000000 | |
//438000000000 | |
//565200000000 | |
//378800000000 | |
//2359500000000 | |
//549800000000 | |
//529200000000 | |
//1988100000000 | |
//7762500000000 | |
//1091412000000 | |
//1675200000000 | |
//0 4 0.1 | |
//0 5 0.093 | |
//0 9 0.034 | |
//0 11 0.093 | |
//1 0 0.05 | |
//1 5 0.046 | |
//1 6 0.173 | |
//1 9 0.046 | |
//1 11 0.046 | |
//2 1 0.137 | |
//2 9 0.277 | |
//2 10 0.062 | |
//3 2 0.568 | |
//3 5 0.006 | |
//3 6 0.021 | |
//3 10 0.026 | |
//3 11 0.05 | |
//4 0 0.1 | |
//4 3 0.033 | |
//4 6 0.125 | |
//4 9 0.034 | |
//5 4 0.033 | |
//5 8 0.013 | |
//5 10 0.153 | |
//6 5 0.136 | |
//6 9 0.387 | |
//6 11 0.022 | |
//7 6 0.345 | |
//7 5 0.0061 | |
//7 4 0.285 | |
//7 11 0.015 | |
//8 7 0.048 | |
//8 10 0.09 | |
//8 11 0.03 | |
//9 8 0.01 | |
//9 5 0.079 | |
//9 3 0.079 | |
//9 11 0.039 | |
//10 9 0.12 | |
//11 10 0.084 | |
//11 5 0.183 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment