QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261487#7753. Energy DistributionyinwuxiaoWA 0ms4052kbC++143.4kb2023-11-22 22:19:372023-11-22 22:19:38

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-11-22 22:19:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4052kb
  • [2023-11-22 22:19:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
const double eps = 1e-6;

int n,m;
double a[N][N];
int c[N],b[N][N],d[N][N];
double w[N];
int gauss() {
    int c, r;
    for (c = 0, r = 0; c < n; ++c) {        // c列r行,遍历列
        int t = r;
        
        for (int i = r; i < n; ++i)         // 寻找列主元,拿t记录
            if (fabs(a[i][c]) > fabs(a[t][c])) 
                t = i;              
        
        if (fabs(a[t][c]) < eps) continue;  // 如果列主元为0,不必考虑,当前列全为0
        
        // 交换列主元t行与当前r行的数
        for (int i = c; i < n + 1; ++i) swap(a[t][i], a[r][i]); 
        // 当前列主元已经被交换到了r行,需要从后向前进行处理,避免主对角线元素变成1
        for (int i = n; i >= c; --i) a[r][i] /= a[r][c]; 
        
        // 列主消元
        for (int i = r + 1; i < n; ++i) 
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; --j) 
                    a[i][j] -= a[r][j] * a[i][c];
                    
        ++r;
    }
    // for (int i=0;i<n;i++){
    //   for (int j=0;j<n+1;j++)
    //     cout<<a[i][j]<<" ";
    //   cout<<endl;
    // }
    // if (r < n) {
    //     for (int i = r; i < n; ++i) 
    //         if (fabs(a[i][n]) > eps) return 2;  // 0x=1 则无解
        
    //     // return 1;   // 0x=0 无穷多解
    // }
    
    // 上三角阶梯型矩阵
    // 直接求解即可,最后一列放置结果
    for (int i = n - 1; i >= 0; --i) 
    {
        int jl=-1;
        for (int j=0;j<n;j++) if (a[i][j]>0) {jl=j; break;}
        for (int j = i + 1; j < n; ++j) 
            a[i][n] -= a[j][n] * a[i][j];
        if (jl!=-1&&jl!=i){
          a[jl][n]=a[i][n];
          a[i][n]=0;
        }
   	}
    return 0;
}
int fa[N];
int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
double solve(int x){
    int cnt=0;
    for (int i=1;i<=m;i++) 
      if (find(i)==x) c[++cnt]=i;
    n=cnt;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        d[i][j]=b[c[i]][c[j]];
    memset(a,0,sizeof(a));
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++)
        a[i][j]=d[i+1][j+1];
      a[i][n]=1;
    }
    for (int i=0;i<n;i++) a[n][i]=1;
    a[n][n+1]=-1;
    n++;
//    for (int i=0;i<n;i++){
//      for (int j=0;j<n+1;j++)
//        cout<<a[i][j]<<" ";
//    	cout<<endl;
//	}
    int t = gauss();
    n--;
    for (int i=0;i<n;i++) w[i+1]=a[i][n+1];
//    for (int i=1;i<=n+1;i++) cout<<w[i]<<endl;
    double ans=0;
    for (int i=1;i<=n;i++)
      for (int j=i;j<=n;j++)
        ans+=d[i][j]*w[i]*w[j];
    return ans;
}
int main() {
    cin >> n;
    m=n;
    int cnt=0;
    for (int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
    	int sum=0;
        for (int j=1;j<=n;j++){
        	cin>>b[i][j];
        	sum+=b[i][j];
          if (b[i][j]>0){
            fa[find(i)]=find(j);
          }
        }
    }
    double ans=0;
    for (int i=1;i<=m;i++) ans=max(ans,solve(i));
    printf("%.8lf", ans);
//    if (t == 0) {
//        for (int i = 0; i < n; ++i) printf("%.2lf\n", a[i][n]);
//    } 
//    else if (t == 1) puts("Infinite group solutions");
//    else puts("No solution");
    
    return 0;
}
/*
6
0 0 1 1 0 0
0 0 1 1 0 0
1 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0


4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4052kb

input:

2
0 1
1 0

output:

0.25000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.57142857

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4048kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.50000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3868kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

0.42857143

result:

wrong answer 1st numbers differ - expected: '0.7500000', found: '0.4285714', error = '0.3214286'