oj.uz

답안 #3946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3946 2013-08-31T09:36:34 Z Apple_Cplus Following Flow (kriii1_F) C++
1 / 1
 0 ms 1684 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
 
using namespace std;

#define EPS 1e-9

vector<int> adj[33];
vector<int> wht[33];
int in[33],out[33];
int n,m;

double a[33][33],b[33];
void gauss() {
	for(int i=0;i<=n;++i) {
		double mx = 0; int idx = -1;
		for(int j=i;j<=n;++j) if(abs(a[j][i]) > mx) {
			mx = abs(a[j][i]);
			idx = j;
		}
		for(int j=0;j<=n;++j) swap(a[i][j],a[idx][j]);
		swap(b[i],b[idx]);
		double tt = a[i][i];
		for(int k=i;k<=n;++k) a[i][k] /= tt;
		b[i] /= tt;
		for(int j=0;j<=n;++j) if(j != i && abs(a[j][i]) > EPS) {
			double tmp = a[j][i];
			for(int k=0;k<=n;++k) {
				a[j][k] -= tmp * a[i][k];
			} b[j] -= tmp * b[i];
		}
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i) {
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		adj[u].push_back(v);
		wht[u].push_back(w);
		out[u]++, in[v]++;
	}

	for(int u=0;u<=n;++u) {
		a[u][u] = 1;
		for(int i=0;i<adj[u].size();++i) {
			int v = adj[u][i];
			int w = wht[u][i];
			a[u][v] += -1.0/out[u];
			b[u] += 1.0 * w / out[u];
		}
	} 
	
	gauss();
	printf("%.10lf",b[0]);
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1684 KB Output is correct
2 Correct 0 ms 1684 KB Output is correct
3 Correct 0 ms 1684 KB Output is correct
4 Correct 0 ms 1684 KB Output is correct
5 Correct 0 ms 1684 KB Output is correct
6 Correct 0 ms 1684 KB Output is correct
7 Correct 0 ms 1684 KB Output is correct
8 Correct 0 ms 1684 KB Output is correct
9 Correct 0 ms 1684 KB Output is correct
10 Correct 0 ms 1684 KB Output is correct
11 Correct 0 ms 1684 KB Output is correct
12 Correct 0 ms 1684 KB Output is correct
13 Correct 0 ms 1684 KB Output is correct
14 Correct 0 ms 1684 KB Output is correct
15 Correct 0 ms 1684 KB Output is correct