解題區/解題區 - UVa

UVa 215 - Spreadsheet Calculator

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一張 N * M 的試算表，並且給定每一格的值可以倚靠其他欄位的結果。是否存在循環依賴？如果不存在則將每一格的答案計算出，否則將輸出存有循環依賴上的所有格子情形。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0

Sample Output

1
2
3
4
5
6
7
      0     1
A     3     5
B     3    -2
A0: A0
B0: C1
C1: B0+A1

Solution

其實就最簡單就是利用高斯消去找解，但是測資中最討厭的地方在於假使 A0 = A0-A0 這種情況也要算依賴關係，那麼高斯消去仍然找得到所有變數的解。

所以最後還是弄一個 dfs 找是否會抵達環上任何一點。

如果將這些資訊排除，圖就是一個 DAG，不用高斯消去也是相當容易的模擬計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
void gaussianElimination(double mtx[][256], int n, double sol[], int nosol[]) {
#define eps 1e-6
    int i, j;		
    for(i = 0; i < n; i++) {
        int k = i;
        for(j = i; j < n; j++)
            if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                k = j;
        if(fabs(mtx[k][i]) < eps)
            continue;
        if(k != i) {
            for(j = 0; j <= n; j++)
                swap(mtx[k][j], mtx[i][j]);
        }
        for(j = 0; j < n; j++) {
            if(i == j)  continue;
            for(k = n; k >= i; k--) {
                mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
    }	
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j <= n; j++)
//			printf("%lf ", mtx[i][j]);
//		puts("");
//	}
    for(int i = 0; i < n; i++)
    	nosol[i] = 0;
    for(i = n-1; i >= 0; i--) {
        if(fabs(mtx[i][i]) < eps)
            nosol[i] = 1;
        else {
            if(fabs(mtx[i][n]) < eps)
                sol[i] = 0;
            else
                sol[i] = mtx[i][n]/mtx[i][i];
        }
        for(j = i+1; j < n; j++)
            if(fabs(mtx[i][j]) > eps && nosol[j])
                nosol[i] = 1;
    }
}
vector<int> depend[512];
int visited[512], in_stk[512];
int dfs(int u, int p) {
    visited[u] = 1, in_stk[u] = 1; 
    for(int i = 0; i < depend[u].size(); i++) {
        int v = depend[u][i];
        if(in_stk[v])	return 1;
        if(visited[v] == 0 && dfs(v, u))
            return 1;
    }
    in_stk[u] = 0;
    return 0;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int N, M;
    char s[1025], exp[32][32][128];
    while(scanf("%d %d", &N, &M) == 2 && N+M) {
        while(getchar() != '\n');
        
        int notsolvable[256];
        double f[256][256] = {}, value[256];
        
        for(int i = 0; i < N * M; i++) {
            depend[i].clear();
        }
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                scanf("%s", s);
                strcpy(exp[i][j], s);
                int sign = 1;
                f[i * M + j][i * M + j] = 1;
                for(int k = 0; s[k]; k++) {
                    if(s[k] == '+')			sign = 1;
                    else if(s[k] == '-')	sign = -1;
                    else if('0' <= s[k] && s[k] <= '9') {
                        int num = 0;
                        while('0' <= s[k] && s[k] <= '9')
                            num = num * 10 + s[k] - '0', k++;
                        k--;
                        f[i * M + j][N * M] += sign * num;
                    } else {
                        int rol = s[k] - 'A', num = 0;
                        k++;
                        while('0' <= s[k] && s[k] <= '9')
                            num = num * 10 + s[k] - '0', k++;
                        k--;
                        f[i * M + j][rol * M + num] -= sign;
                        depend[i * M + j].push_back(rol * M + num);
                    }
                }
            }
        }
        gaussianElimination(f, N*M, value, notsolvable);
        for(int i = 0; i < N*M; i++) {
            memset(visited, 0, sizeof(visited));
            memset(in_stk, 0, sizeof(in_stk));
            notsolvable[i] |= dfs(i, i);
        }
        int allsol = 1;
        for(int i = 0; i < N*M; i++) {
//			printf("%lf %d\n", value[i], notsolvable[i]);
            allsol &= !notsolvable[i];
        }
        if(allsol) {
            printf(" ");
            for(int i = 0; i < M; i++)
                printf("%6d", i);
            puts("");
            for(int i = 0; i < N; i++) {
                printf("%c", i + 'A');
                for(int j = 0; j < M; j++)
                    printf("%6d", (int)value[i * M +j]);
                puts("");
            }
        } else {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(notsolvable[i * M + j]) {
                        printf("%c%d: %s\n", i + 'A', j, exp[i][j]);
                    }
                }
            }
        }
        puts("");
    } 
    return 0;
}
/*
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0
*/