Pagini recente » Cod sursa (job #1675322) | Cod sursa (job #2947251) | Cod sursa (job #354688) | Cod sursa (job #2115402) | Cod sursa (job #2478880)
#include <bits/stdc++.h>
using namespace std;
bool X[505];
bool A[505][505];
inline int Mod(int nr) {
if(nr < 0)
return -nr;
return nr;
}
inline void solve() {
int N, M, l;
scanf("%d%d%d", &N, &M, &l);
vector <int> Size;
Size.push_back(0);
for(int i = 1;i <= N;i++)
for(int j = 1;j <= M + 1;j++)
A[i][j] = 0;
for(int i = 1;i <= M;i++) {
int aux;
scanf("%d", &aux);
Size.push_back(aux);
}
for(int i = 1;i <= l;i++) {
int aux;
scanf("%d", &aux);
A[aux][M + 1] = 1;
}
for(int i = 1;i <= M;i++) {
for(int j = 1;j <= Size[i];j++) {
int aux;
scanf("%d", &aux);
A[aux][i] = 1;
}
}
int i = 1, j = 1;
int k;
bool aux;
while(i <= N && j <= M)
{
//Cautam o linie k pentru care A[k][j] sa fie nenul. Folosim epsilonul pentru a nu lua in considerare micile erori de calcul.
for(k = i; k <= N; ++k)
if(A[k][j] != 0)
break;
//Daca nu gasim linia, necunoscuta j este variabila libera, incrementam pe j si trecem la pasul urmator.
if(k == N+1)
{
++j;
continue;
}
//Interschimbam pe k cu i, daca este cazul.
if(k != i)
for(int l = 1; l <= M+1; ++l)
{
aux = A[i][l];
A[i][l] = A[k][l];
A[k][l] = aux;
}
//Pentru a usura calculele, impartim toate valorile de pe linia i la A[i][j], A[i][j] devenind 1.
//Observam ca valorile de pe linia i si coloanele 1..j-1 sunt egale cu 0 de la pasii precedenti ai algoritmului,
//deci nu e necesar sa le parcurgem pentru a le imparti.
// for(int l = j+1; l <= M+1; ++l)
// A[i][l] = A[i][l] / A[i][j];
// A[i][j] = 1;
//Scadem din ecuatiile i+1...N ecuatia i inmultita cu A[u][j], pentru a egala toti coeficientii de coloana j
//a acestor linii la 0.
for(int u = i+1; u <= N; ++u)
{
for(int l = j+1; l <= M+1; ++l) {
A[u][l] -= A[u][j] & A[i][l];
}
A[u][j] = 0;
}
++i; ++j;
}
//Calculul necunoscutelor
for(int i = N; i>0; --i)
for(int j = 1; j <= M+1; ++j)
if(A[i][j] != 0)
{
//Singura valoare nenegativa de pe linia i este rezultatul => sistemul nu are solutie.
if(j == M+1)
{
printf("-1\n");
return;
}
//Calculam pe necunoscuta j = rezultatul ecuatiei i - necunoscutele j+1...M inmultite cu coeficientii lor din aceasta ecuatie.
X[j] = A[i][M+1];
for(int k = j+1; k <= M; ++k)
X[j] -= X[k] & A[i][k];
break;
}
//Afisare
for(int i = 1; i <= M; ++i) {
if(X[i])
printf("%d ", i);
}
printf("\n");
}
int main() {
freopen("becuriacm.in", "r", stdin);
freopen("becuriacm.out", "w", stdout);
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}