#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>
 
#define MAXN 256
 
using namespace std;
 
const int maxiterruim = 10000; /* Número máximo de iterações sem nenhuma melhora */
const int maxiter = 50000; /* Número máximo de iterações */
const double e = 0.05; /* Tamanho máximo do grupo = (1+e)*N/k */
const double fatortaboo = 0.4; /* O tamanho da lista taboo é N * fatortaboo */
const int maxncand = 100; /* Número máximo de vértices candidatos a mover */
 
int nvertice;
int adj[MAXN][MAXN], peso[MAXN][MAXN];
int pesosoma[MAXN];
 
/* Inicializa com uma partição aleatória */
vector <int> particao_inicial(int k, int& custo, vector <int>& contrib, vector <int>& tamgrupo)
{
	const int n = nvertice;
	vector <int> particao = vector <int> (n, -1);
 
	if (tamgrupo.size() != k)
		tamgrupo = vector <int> (k, 0);
 
	/* Vértices sem partição atribuída */
	vector <int> faltam = vector <int> (n, -1);
	for (int i = 0; i < n; i++)
		faltam[i] = i;
 
	/* Atribuindo aleatoriamente */
	for (int i = 0; i < k; i++) {
		int tam = n/k;
		if (i < (n%k))
			tam ++;
		for (int j = 0; j < tam; j++) {
			int escolhe = rand()%faltam.size();
			particao[faltam[escolhe]] = i;
 
			swap(faltam[escolhe], faltam[faltam.size()-1]);
			faltam.pop_back();
		}
		tamgrupo[i] = tam;
	}
 
	/* Custo da solução */
	if (contrib.size() != n)
		contrib = vector <int> (n, 0);
 
	custo = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (particao[i] != particao[j] && adj[i][j]) {
				custo += peso[i][j];
				contrib[i] += peso[i][j];
			}
	custo /= 2; /* Cada arestra foi contada duas vezes */
 
	return particao;
}
 
/* Qual a diferença de custo total se mover o vértice "i" do grupo atual "anterior" para o grupo "novo" */
int movimento(int i, int novo, vector <int>& particao)
{
	int ret = 0;
	for (int k = 0; k < nvertice; k++) {
		if (particao[k] == particao[i])
			ret += adj[i][k];
		if (particao[k] == novo)
			ret -= adj[i][k];
	}
 
	return ret;
}
 
void atualizar_contrib(int i, int novo, vector <int>& particao, vector <int>& contrib)
{
	for (int k = 0; k < nvertice; k++) {
		if (particao[k] == particao[i]) {
			contrib[i] += adj[i][k];
			contrib[k] += adj[i][k];
		}
		if (particao[k] == novo) {
			contrib[i] -= adj[i][k];
			contrib[k] -= adj[i][k];
		}
	}
}
 
vector <int> taboo_search_k_partition(int k, int& custo)
{
	const int n = nvertice;
 
	vector <int> melhor; /* Melhor solução */
	int customelhor; /* Custo dela */
 
	vector <int> atual; /* Solução atual */
	int custoatual; /* E o custo dela */
 
	int iter = 1, ultimamelhora = 1; /* Iteração atual e última vez que a solução melhorou */
 
	vector <int> contrib(n, 0); /* Com quanto cada vértice contribue para o peso total da solução */
	deque <int> listataboo; /* Vértices que temporariamente não podem ser movidos (vértices taboo) */
	vector <int> taboo(n, 0); /* Se pertence a lista taboo ou não */
	const int T = (int)(n * fatortaboo); /* Tamanho da lista taboo */
 
	vector <int> tamgrupo(n, 0); /* Tamanho de cada grupo */
	const int maxgtam = (int)((1.0+e)*n/k); /* Tamanho máximo de cada grupo */
 
	atual = particao_inicial(k, custoatual, contrib, tamgrupo);
	melhor = atual;
	customelhor = custoatual;
 
	printf("Custo inicial: %d\n", custoatual);
 
	while (iter-ultimamelhora <= maxiterruim && iter <= maxiter) {
		vector <pair <double, int> > potcands; /* Candidatos em potencial */
 
		for (int i = 0; i < n; i++)
			if (!taboo[i])
				potcands.push_back(make_pair(1.0*contrib[i]/pesosoma[i], i));
 
		partial_sort(potcands.begin(), min(potcands.end(), potcands.begin()+maxncand), potcands.end(), greater <pair <int, int> >());
 
		int mindiff = 2000000000; /* Inf */
		int ncand = min((int)potcands.size(), maxncand);
		pair <int, int> best = make_pair(-1, -1);
 
		for (int i = 0; i < ncand; i++) {
			int cand = potcands[i].second;
			for (int j = 0; j < k; j++)
				if (tamgrupo[j] < maxgtam) {
					int diff = movimento(cand, j, atual);
					if (diff < mindiff) {
						mindiff = diff;
						best = make_pair(cand, j);
					}
				}
		}
 
		if (best == make_pair(-1, -1)){
			printf("\n");
			printf("Sem movimentos.\n");
			break;
		}
 
		int i = best.first, j = best.second;
		int anterior = atual[i];
 
		int diff = movimento(i, j, atual);
		custoatual += diff;
		atual[i] = j;
		if (custoatual < customelhor) {
			customelhor = custoatual;
			melhor = atual;
			ultimamelhora = iter;
			printf("\nMELHORA: Custo atual: %d (iteracao %d)\n", custoatual, iter);
		}
		tamgrupo[anterior] --;
		tamgrupo[j] ++;
 
		taboo[i] = 1;
		listataboo.push_back(i);
		if ((int)listataboo.size() > T) {
			int v = listataboo.front();
			listataboo.pop_front();
			taboo[v] = 0;
		}
 
		atualizar_contrib(i, j, atual, contrib);
 
		if (diff) {
			printf(" %lld ", custoatual);
			fflush(stdout);
		}
 
		iter ++;
	}
	printf("\n");
	if (iter-ultimamelhora > maxiterruim)
		printf("Muito tempo sem melhora.\n");
	if (iter > maxiter)
		printf("Numero maximo de iteracoes atingido.\n");
 
	custo = customelhor;
 
	return melhor;
}
 
char line[10240000];
int main(int argc, char ** argv)
{
	int k;
printf("Teste.\n");
system("pause");
 FILE * fin = fopen("input", "r");
 if (fin == NULL) {
         printf("Err.\n");
         system("pause");
         return 0;
 
         }
   /* Tenta ai */
 
   printf("ok.\n");
 
#if 1
	int narestra;
	fgets(line, 1024, fin);
	sscanf(line, "%d %d", &nvertice, &narestra);
 
	const int n = nvertice;
 
	memset(adj, 0, sizeof(adj));
	for (int i = 0; i < n; i++) {
		fgets(line, 1024, fin);
		istringstream iss(line);
		int j;
		pesosoma[i] = 0;
		while (iss >> j) {
			adj[i][j-1] = 1;
			pesosoma[i] += 1;
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (adj[i][j])
				peso[i][j] = 1;
			else
				peso[i][j] = 0;
 
	k = 10;
#else /* Depois tem que atualizar isto aqui tambm */
	scanf("%d %d", &nvertice, &k);
 
	const int n = nvertice;
 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &adj[i][j]);
 
	for (int i = 0; i < n; i++) {
		pesosoma[i] = 0;
		for (int j = 0; j < n; j++) {
			scanf("%d", &peso[i][j]);
			pesosoma[i] += peso[i][j];
		}
	}
#endif
 
printf("Lido.\n");
system("pause");
 
	srand(time(NULL));
 
	int custo;
	vector <int> part = taboo_search_k_partition(k, custo);
 
	for (int j = 0; j < k; j++) {
		int tam = 0;
 
		for (int i = 0; i < n; i++)
			if (part[i] == j)
				tam ++;
 
		printf("Grupo %d (tamanho = %d):", j+1, tam);
		for (int i = 0; i < n; i++)
			if (part[i] == j)
				printf(" %d", i+1);
		printf("\n");
	}
	printf("Custo total: %lld\n", custo);
	while (1) {}
 
system("sleep 10");
    system("pause");
 
	return 0;
}