Cod sursa(job #491774)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 12 octombrie 2010 13:54:22
Problema Radiatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
FILE *f=fopen("radiatie.in","r");
FILE *g=fopen("radiatie.out","w");
int n,m,k,i,r1,r2,t[15001],cm[15001],nrt[15001],myn,p[15001],viz[15001],x,y,nrx,nry,cmax;
struct nod{
	int a;
	int b;
	int c;
} v[30001];
bool cmp(nod a,nod b){
   return (a.c < b.c);
}
int max(int l,int r){
   if(l>r)
	    return l;
   return r;
}
vector < pair<int,int> > a[15001];
void citire(){
	fscanf(f,"%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++)
	fscanf(f,"%d%d%d",&v[i].a,&v[i].b,&v[i].c);	
}

void apm(){
	int i;
	for(i=1;i<=n;i++)
		t[i]=-1;
	int k=0;
	i=1;
	while(k < n-1){
		  r1=v[i].a;
		  r2=v[i].b;
	while(t[r1]>0){
		r1=t[r1];
	}
	while(t[r2]>0){
		r2=t[r2];
	}
	if(r1!=r2){
		  if(t[r1] < t[r2] ){
			    t[r1]+=t[r2];
				t[r2]=r1;	
                cm[r2]=v[i].c;				
		  }
		else { t[r2]+=t[r1];
			   t[r1]=r2;
		       cm[r1]=v[i].c;
		}
	k++;
	
	}
i++;
}
}
void df(int k){
	if(nrt[k]!=0)
		return;
	if(t[k]<0){
		nrt[k]=1;
		return ;
	}
	df(t[k]);
	nrt[k]=nrt[t[k]]+1;
		
}
	
	

int main(){
	citire();
	sort(v+1,v+m+1,cmp);
	apm();
	for(i=1;i<=n;i++)
	if(nrt[i]==0)
		df(i);
	for(int i=1;i<=k;i++){
		fscanf(f,"%d%d",&x,&y);
		cmax=0;		
	    while(nrt[x]>nrt[y]){
			if(cm[x]>cmax)
				cmax=cm[x];
			x=t[x];
		}
		while(nrt[y]>nrt[x]){
			if(cm[y]>cmax)
				  cmax=cm[y];
			y=t[y];
		}
		while(x!=y){
			if(cm[y]>cmax)
				  cmax=cm[y];
			if(cm[x]>cmax)
				cmax=cm[x];
			x=t[x];
			y=t[y];
		}
	fprintf(g,"%d\n",cmax);
	}
return 0;
}