유동자본.cpp

//파급효과
//
//기업의 수 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