POJ 2947 高斯消元--判断一解多解无解

又是偷来的代码，但是第一道高斯消元，纪念下

知道每条式子的结果取模后的值，求方程组，这不同于一般的高斯消元，而且答案必须为整数并在一定区间内

1.由于是整数要用到gcd；

2.解的判断：

有解的情况都是必须满足row一下全为0

一解：化简后是严格的三角矩阵

多解：自由变量个数较少

无解：row以下有非0的

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include<iterator>
#include <algorithm>
#include <string>
using namespace std;
#define N 305
char day[][20]={"","MON","TUE","WED","THU","FRI","SAT","SUN"};
int n,m,k,mat[N][N],ans[N];

int gcd(int a,int b)
{
	if(b==0)
		return a;
	else return gcd(b,a%b);
}
bool mul_solu;
bool gauss(int mat[N][N],int m,int n)
{
	mul_solu=false;
	int row,col;
	for(row=0,col=0;row<m && col<n;++row,++col)
	{
		int p=row;
		for(int j=row+1;j<m;++j)
			if(abs(mat[j][col])>abs(mat[p][col]))
				p=j;
		if(p!=row)
		{
			for(int j=0;j<=n;++j)
				swap(mat[row][j],mat[p][j]);
		}
		if(mat[row][col]==0) // 最大的都为0，说明这一列以下全是0
		{
			row--;
			continue;
		}
		for(int j=row+1;j<m;++j)
		{
			int gg=gcd(mat[row][col],mat[j][col]);
			int muli=mat[j][col]/gg%7;
			int mulj=mat[row][col]/gg%7;
			for(int k=col;k<=n;++k)
			{
				mat[j][k]=mat[j][k]*mulj-mat[row][k]*muli;
				mat[j][k]=(mat[j][k]%7+7)%7;
			}
		}
	}
	for(int i=row;i<m;++i) // inconsistent必须先与multiple判断
		if(mat[i][n])
			return false;
	if(row<n) // free variable 少
	{
		mul_solu=true;
		return true;
	}
	
	for(int i=n-1;i>=0;--i)
	{
		bool flag=false;
		for(int j=3;j<=9;++j)
		{
			int rr=0;
			for(int k=i+1;k<n;++k)
				rr+=mat[k][n]*mat[i][k]%7,rr%=7;
			rr+=j*mat[i][i];
			if(rr%7==mat[i][n])
			{
				mat[i][n]=j;
				flag=true;
				break;
			}
		}
		if(!flag)
			return false;
	}

	return true;
}

int get_time(char *t1,char *t2)
{
	int st,ed;
	for(int i=1;i<=7;++i)
	{
		if(strcmp(t1,day[i])==0)
			st=i;
		if(strcmp(t2,day[i])==0)
			ed=i;
	}
	if(ed-st>=0)
		return ed-st+1;
	else return ed+8-st;
}
char t1[10],t2[10];
int tt;
int main ()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0 && m==0) break;
		memset(mat,0,sizeof(mat));
		for(int i=0;i<m;++i)
		{
			scanf("%d%s%s",&k,t1,t2);
			mat[i][n]=get_time(t1,t2)%7;
			for(int j=1;j<=k;++j)
			{
				scanf("%d",&tt);
				mat[i][tt-1]++;
				mat[i][tt-1]%=7;
			}
		}
		if(gauss(mat,m,n))
		{
			if(mul_solu)
			{
				printf("Multiple solutions.\n");
			}
			else
			{
				for(int i=0;i<n-1;++i)
					printf("%d ",mat[i][n]);
				printf("%d\n",mat[n-1][n]);
			}
		}
		else printf("Inconsistent data.\n");
	}
	return 0;
}