Submission #3937

#	Time	Username	Problem	Language	Result	Execution time	Memory
3937		Apple_Cplus	Following Flow (kriii1_F)	C++98	0 / 1	0 ms	1684 KiB

F

#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=0;j<=n;++j) if(abs(a[j][i]) > mx) {
			mx = abs(a[j][i]);
			idx = j;
		}
		swap(a[i],a[idx]), swap(b[i],b[idx]);
		for(int j=0;j<=n;++j) if(j != i && abs(a[j][i]) > EPS) {
			double tmp = a[j][i]/a[i][i];
			for(int k=i;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("%.7lf",b[0]);
}

• Subtask 1: 0 / 1