转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
继续高斯消元
建立方程
A11*X1+A12*X2+……A1N*XN同余B1%7
A21*X1+A22*X2+……A2N*XN同余B2%7
AM1*X1+AM2*X2+……AMN*XN同余BM%7
然后便是高斯消元解这个方程,
无解情况,出现一行系统全为0,等式右边却不为0。
多解情况,变元个数大于方程个数
否则为一解情况,解出方程的解便可
/*
ID:cxlove
PROB:poj 2947
DATA:2012.3.31
HINT:高斯消元
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[305][305];
int change(char s[10]){
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;
}
void gauss(){
int i,j;
int ans[305];
for(i=0,j=0;i<m&&j<n;j++){
int k;
for(k=i;k<m;k++)
if(a[k][j])
break;
if(a[k][j]){
for(int r=j;r<=n;r++)
swap(a[k][r],a[i][r]);
for(int r=0;r<m;r++)
if(r!=i&&a[r][j]){
int b1=a[i][j],b2=a[r][j];
for(int t=0;t<=n;t++)
a[r][t]=((a[r][t]*b1-a[i][t]*b2)%7+7)%7;
}
i++;
}
}
for(int k=i;k<m;k++)
if(a[k][n]){
printf("Inconsistent data.\n");
return;
}
if(i<n){
printf("Multiple solutions.\n");
return ;
}
/*for(int i=0;i<m;i++){
for(int j=0;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
for(i=n-1;i>=0;i--){
int temp=a[i][n];
for(j=i+1;j<n;j++)
temp=((temp-a[i][j]*ans[j])%7+7)%7;
while(temp%a[i][i]!=0)temp += 7;
ans[i]=(temp/a[i][i])%7;
}
for(i=0;i<n;i++)
if(ans[i]<3)
ans[i]+=7;
for(i=0;i<n-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n-1]);
}
int main(){
char str1[10],str2[10];
while(scanf("%d%d",&n,&m)!=EOF&&n+m){
memset(a,0,sizeof(a));
for(int i=0;i<m;i++){
int k;
scanf("%d%s%s",&k,str1,str2);
a[i][n]=(change(str2)-change(str1)+1+7)%7;
while(k--){
int num;
scanf("%d",&num);
a[i][num-1]++;
}
for(int j=0;j<n;j++)
a[i][j]%=7;
}
/*for(int i=0;i<m;i++){
for(int j=0;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
gauss();
}
return 0;
}
分享到:
相关推荐
北大POJ3436-ACM Computer Factory 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码