Cod sursa(job #491772)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 12 octombrie 2010 13:50:38
Problema Radiatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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,tt,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]=i;
	int k=0;
	for(i=1;i<=m;i++){
	 r1=v[i].a;
     r2=v[i].b;
      while(t[r1]!=r1)
           r1=t[r1];
	  while(t[r2]!=r2)
		   r2=t[r2];
	 if(r1!=r2){
		t[r2]=r1;
		cm[r2]=v[i].c;		 
	 }
	}

}
void df(int k){
	if(nrt[k]!=0)
		return;
	if(t[k]==k){
		nrt[k]=1 ; return; }
	
		df(t[k]);
		nrt[k]=nrt[t[k]]+1;
	
	
}
	
	

int main(){
	citire();
	sort(v+1,v+m+1,cmp);
	apm();
	//nrt[tt]=1;
	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;
}