本文主要是介绍[POJ2947] Widget Factory 高斯消元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
通过每个人列方程 把系数模7来防止溢出 最后除法的时候用逆元算一下
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#define SF scanf
#define PF printf
using namespace std;
typedef long long LL;
const int MAXN = 300;
inline int abs(int x) { return x > 0 ? x : -x; }
inline int gcd(int a, int b)
{ while(b) { int r = a % b; a = b; b = r; } return a;
}
inline int lcm(int a, int b)
{return a / gcd(a, b) * b;
}
int Ans[MAXN+10];
int Niyuan[] = { 0, 1, 4, 5, 2, 3, 6 };
char s[10], ss[10];
template <int maxn, int maxm>
struct Maxtrix{int equ, var;int A[maxn+10][maxm+10];void init() { memset(A, 0, sizeof(A)); equ = var = 0; }int Gauss(int equ, int var) {int row, col;for(row = 0, col = 0; row < equ && col < var; row++, col++){int r = row;for(int i = row+1; i < equ;i++)if(abs(A[i][col]) > abs(A[r][col]))r = i;if(A[r][col] == 0) {row--;continue;}if(r != row) for(int i = 0; i <= var; i++) swap(A[r][i], A[row][i]);for(int i = row+1; i < equ; i++){if(!A[i][col]) continue;int LCM = lcm(abs(A[row][col]), abs(A[i][col]));int ta = LCM / abs(A[i][col]);int tb = LCM / abs(A[row][col]);if(A[row][col] * A[i][col] < 0) tb = -tb;for(int j = col; j <= var; j++)A[i][j] = ((A[i][j] * ta - A[row][j] * tb) % 7 + 7) % 7;}}for(int i = row; i < equ; i++) if(A[i][var]) return -1;if(row < var) return 1;for(int i = var-1; i >= 0; i--){int tmp = A[i][var];for(int j = i+1; j < var;j++)if(A[i][j] != 0)tmp = ((tmp - A[i][j] * Ans[j]) % 7 + 7) % 7;Ans[i] = (tmp * Niyuan[A[i][i]]) % 7;}return 0;}
};
Maxtrix <MAXN, MAXN> A;
int Num(char s[])
{if(strcmp(s,"MON") == 0) return 1;else if(strcmp(s,"TUE")==0) return 2;else if(strcmp(s,"WED")==0) return 3;else if(strcmp(s,"THU")==0) return 4;else if(strcmp(s,"FRI")==0) return 5;else if(strcmp(s,"SAT")==0) return 6;else return 7;
}
int main()
{int n, m;while(SF("%d%d", &n, &m) == 2 && (n || m)){memset(A.A, 0, sizeof(A.A)); A.equ = m; A.var = n;for(int i = 0; i < m; i++){int k;SF("%d%s%s", &k, s, ss);int u = Num(s), v = Num(ss);A.A[i][n] = ((v - u + 1) % 7 + 7) % 7;for(int j = 1; j <= k; j++){SF("%d", &u); u--;A.A[i][u] = (A.A[i][u] + 1) % 7;}}int ans = A.Gauss(m, n);if(ans == 0) {for(int i = 0; i < n; i++) if(Ans[i] <= 2) Ans[i] += 7;for(int i = 0; i < n; i++)if(i == n-1) PF("%d\n", Ans[i]);else PF("%d ", Ans[i]);}else if(ans == -1) PF("Inconsistent data.\n");else PF("Multiple solutions.\n");}
}这篇关于[POJ2947] Widget Factory 高斯消元的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
