가공자본 구하기.cpp

//가공자본 구하기
//자본금(대변) 100억 A회사에서 80억을 출자해 B회사 설립의 자본금(대변)으로 기록되었다.
//B회사 주식 80억은 A회사의 자산(차변)으로 기록된다.
//여전히 A회사의 자본금(대변)은 100억원이다.
//A회사와 B회사의 자본 총합은 180억원이되므로
//이때 80억은 가공자본이라 한다.
//기업의 지배 구조가 방향 그래프로 주어졌을때, 가공자본의 규모를 계산하시오.
//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){
    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];
            sum=(lint)(sum/1000)*1000; //1000원 미만은 버림
            //printf("***%lld\n",sum);
            set(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;
    }
    
//    lint max=0;
//    int c=0;
//    for(int i=0; i<n; i++){
//        k=i;
//        set(i);
//        printf("%lld\n", sum);
//        if(max<sum) {max=sum; c=i;}
//        sum=0;
//        for(int i=0; i<n; i++)
//            for(int j=0; j<n; j++)
//                chk[i][j]=0;
//        for(int i=0; i<n; i++)
//            visited[i]=0;
//    }
//    printf("\n%d\n%lld",c,max);
    set(0);
    
    printf("\n\n%lld\n%lld", sum,total_cap);
}

//3 3
//1000000
//2000000
//3000000
//0 1 0.5
//1 2 0.5
//2 0 0.5

//5 9
//100000000
//0
//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

//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