图图

C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 708K, 提交时间: 2019-08-06 14:45:52

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
double a[MAXN][MAXN];//增广矩阵
double x[MAXN];//解集
int ans[MAXN];
int p[105];
double isp = 1e-5;
double ispx = 1e-11;
bool ji[105];
int Gauss(int equ, int var) {
	int i, j, k;
	int max_r;// 当前这列绝对值最大的行.
	int col;//当前处理的列
	double ta;
	double temp;
	//转换为阶梯阵.
	col = 0; // 当前处理的列
	for (k = 0; k < equ && col < var; k++, col++) {
		max_r = k;
		for (i = k + 1; i < equ; i++) {
			if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i;
		}
		if (max_r != k) {// 与第k行交换.
			for (j = 0; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
		}
		if (fabs(a[k][col]) <= ispx) {                     
			continue;
		}
		for (int g= 0; g < equ; g++) {
			if (g != k)
			{
				ta = a[g][col] / a[k][col];
				//if (a[i][col] * a[k][col] < 0)ta = -ta;//异号的情况是相加
				for (int j = equ; j >=k; j--) {
					a[g][j] = a[g][j] - a[k][j] * ta;
				}
			}
		}
	}
	return 0;
}
int main(void) {
	int i, j;
	int equ, var;
	scanf("%d%d", &equ, &var);
	memset(a, 0, sizeof(a));
	int x1, y1, val;
	for (j = 0; j < var; j++) {
		scanf("%d%d%d", &x1, &y1, &val);
		ji[y1] = 1;
		a[y1][x1] = 1.0*val;
		ans[x1] += val;
	}
	ll minlcm = 1;
	for (int i = 0; i < equ; i++)
	{
		for (int j = 0; j < equ; j++)
		{
			if (!ans[j])
			{
				a[j][j] = 1;
				ans[j] = 1;
			}
			a[i][j] = a[i][j] / (1.0*ans[j]);
		}
	}
	for (int i = 0; i < equ; i++)
	{
		a[i][i] -= 1;
		a[i][equ] = 0;
	}
	for (int i = 0; i <= equ; i++)
		a[equ][i] = 1;
	int free_num = Gauss(equ + 1, equ);
		if (fabs(a[equ][equ]) > ispx)  free_num= -1;
	if (free_num == -1)puts("Impossible");
	else {
		for (int i = 0; i < equ; i++)
		{
			if (fabs(a[i][equ]) < ispx) printf("%.20lf\n", 0.0);
			else printf("%.20lf\n", a[i][equ] / a[i][i]);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 896K, 提交时间: 2018-02-12 15:46:27

#include <bits/stdc++.h>

using namespace std;
const int N = 205;
const double eps = 1e-12;
int n,g[N][N],sum[N];
double a[N][N],del;

bool gauss()
{
	for(int i=1;i<=n;i++){
		int k=i;
		for(int j=i+1;j<=n+1;j++)if(fabs(a[j][i])>fabs(a[k][i])) k=j;
		if(fabs(del=a[k][i])<eps) continue;
		for(int j=i;j<=n+1;j++)swap(a[i][j],a[k][j]);
		for(int j=i;j<=n+1;j++) a[i][j]/=del;
		for(k=1;k<=n+1;k++)if(k!=i){
			del=a[k][i];
			for(int j=i;j<=n+1;j++)a[k][j]-=del*a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		if(fabs(a[i][i])<eps&&fabs(a[i][n+1])>eps) return 0;
	}if(fabs(a[n+1][n+1])>eps) return 0;
	return 1;
}
int main()
{
	int m,u,v,w;scanf("%d%d",&n,&m);int chu[N]={0};
	memset(g,0,sizeof(g));memset(sum,0,sizeof(sum));
	for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);u++;v++;g[u][v]=w;sum[u]+=w;chu[u]++;}
	for(int i=1;i<N;i++) for(int j=1;j<N;j++) a[i][j]=0.0;
	for(int i=1;i<=n;i++){
		if(chu[i]) for(int j=1;j<=n;j++){if(g[i][j]) a[j][i]+=g[i][j]*1.0/(sum[i]*1.0);}
		else a[i][i]+=1.0;
	}
	for(int i=1;i<=n;i++) a[i][i]-=1.0;
	for(int i=1;i<=n;i++) a[n+1][i]=1.0;a[n+1][n+1]=1.0;
	if(!gauss()) printf("Impossible\n");
	else{
		int flag=1;for(int i=1;i<=n;i++) if(a[i][n+1]<-eps) flag=0;
		if(!flag){printf("Impossible\n");exit(0);}
		for(int i=1;i<=n;i++) if(fabs(a[i][n+1])<eps) a[i][n+1]=0.0;
		for(int i=1;i<=n;i++) printf("%.20lf\n",fabs(a[i][n+1]));
	}
	return 0;
}
/*
5
5
0 1 1
1 2 2
2 3 3
3 4 4
4 0 5
*/

详情