Seletiva IOI 2013

superfat.cpp

// Ivan Carvalho
// Superfaturamento - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define PESO first
#define U second.first
#define V second.second
#define PB push_back
#define MP make_pair
#define MAX 1001
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int pai[MAX],peso[MAX],grafo[MAX][MAX],n,menor,delta=999999999;
vector<iii> lista,escolhido;
int find(int x){
	//printf("Find\n");
	if (x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}
void join(int x, int y){
	//printf("Join\n");
	x = find(x);
	y = find(y);
	if (x==y) return;
	if (peso[x]>peso[y]){
		pai[y] = x;
		return;
	}
	if (peso[x]<peso[y]){
		pai[x] = y;
		return ;
	}
	else {
		pai[x] = y;
		peso[y]++;
		return ;
	}
	return ;
}
void prep(){
	//printf("Prep\n");
	for(int i= 1;i<=n;i++){
		peso[i] = 1;
		pai[i] = i;
	}
}
int Kruskal(iii proibido){
	//printf("Kruskal\n");
	int resposta = 0;
	prep();
	int conjuntos = 1;
	for(int i = 0;conjuntos!=n;i++){
		if (lista[i]==proibido) continue;
		if (find(lista[i].U) != find(lista[i].V)){
			conjuntos++;
			resposta += lista[i].PESO;
			join(lista[i].U,lista[i].V);
		}
	}
	return resposta;
}
int main(){
	int contador = 1; 
	scanf("%d",&n);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&grafo[i][j]);
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) lista.PB(MP(grafo[i][j],MP(i,j)));
	sort(lista.begin(),lista.end());
	prep();
	//printf("Lista : %d\n",(int)lista.size());
	for(int i = 0;contador!=n;i++){
		//printf("pai 1: %d pai 2 : %d\n",find(lista[i].U),find(lista[i].V));
		if (find(lista[i].U) != find(lista[i].V)){
			//printf("Entrou\n");
			contador++;
			menor += lista[i].PESO;
			join(lista[i].U,lista[i].V);
			escolhido.PB(lista[i]);
		}
		//printf("Contador : %d Menor : %d\n",contador,menor);
	}
	//printf("Primeiro : %d\nEscolhido : %d\n",menor,(int)escolhido.size());
	for(int k=0;k<escolhido.size();k++) {
		//printf("K : %d\n",k);
		delta = min(delta,Kruskal(escolhido[k]));
	}
	printf("%d\n",delta - menor);
	return 0;
}