ACM.algorithm.rar_GCD矩阵_匈牙利_区间匹配_最短路 三维_模板元

#include<stdio.h> #include<stdlib.h> #include<string.h> #define Max_len 100005 typedef struct node{ long adjvex; struct node *next; long length; }edgenode; typedef struct{ int num; edgenode *link; }vexnode; typedef struct{ edgenode *front,*rear; }linkqueue; long pre_index[Max_len]; int EMPTY(linkqueue *q){ if(q->front==q->rear) return 1; else return 0; } void ENQUEUEQ(linkqueue *q,long x){ q->rear->next=(edgenode*)malloc(sizeof(edgenode)); q->rear=q->rear->next; q->rear->adjvex=x; q->rear->next=NULL; } long DEQUEUEQ(linkqueue *q){ long temp; edgenode *s; if(EMPTY(q)) return -1; else{ s=q->front->next; if(s->next==NULL){ q->front->next=NULL; q->rear=q->front; } else q->front->next=s->next; temp=s->adjvex; return temp; } } void quick_sort(long x[],long l,long u){ if(l>=u) return; long t=x[l]; long i=l; long j=u+1; long temp; while(1){ do{i++;}while(i<=u&&x[i]<t); do{j--;}while(x[j]>t); if(i>j)break; temp=x[i]; x[i]=x[j]; x[j]=temp; } temp=x[l]; x[l]=x[j]; x[j]=temp; quick_sort(x,l,j-1); quick_sort(x,j+1,u); } struct edge{ long fromvex,endvex; long length; }; void quick_sort_2(edge x[],int l,int u){ if(l>=u) return; long t=x[l].length; int i=l; int j=u+1; edge temp; while(1){ do{i++;}while(i<=u&&x[i].length<t); do{j--;}while(x[j].length>t); if(i>j)break; temp=x[i]; x[i]=x[j]; x[j]=temp; } temp=x[l]; x[l]=x[j]; x[j]=temp; quick_sort_2(x,l,j-1); quick_sort_2(x,j+1,u); } int main(){ int m,T; int case_count=1; scanf("%d",&T); while(T--){ printf("Case #%d:\n",case_count); case_count++; vexnode ga[Max_len]; long triangle[Max_len]; int sign[Max_len]; edge data[Max_len]; int G[Max_len]; long i,j,k,n,l,i1; scanf("%ld",&n); edgenode *s; for(i=0;i<=n;i++) {ga[i].link=NULL;ga[i].num=0;} for(i=0;i<=n;i++) {sign[i]=0;G[i]=i;} for(i=0;i<n-1;i++){ scanf("%ld%ld%ld",&data[i].fromvex,&data[i].endvex,&data[i].length); } quick_sort_2(data,0,n-2); j=0; i=0; while(j<n-1){ k=data[i].fromvex; l=data[i].endvex; sign[i]=1; if(G[k]==G[l]) sign[i]=2; else{ s=(edgenode*)malloc(sizeof(edgenode)); s->adjvex=data[i].endvex; s->next=ga[data[i].fromvex].link; s->length=data[i].length; ga[data[i].fromvex].link=s; ga[data[i].fromvex].num++; s=(edgenode*)malloc(sizeof(edgenode)); s->adjvex=data[i].fromvex; s->next=ga[data[i].endvex].link; s->length=data[i].length; ga[data[i].endvex].link=s; ga[data[i].endvex].num++; j++; for(i1=0;i1<n;i1++) if(G[i]==G[l]) G[i]=G[k]; } i++; } scanf("%d",&m); int j1; for(j1=0;j1<m;j1++){ long s1,t; scanf("%ld%ld",&s1,&t); linkqueue *q; q=(linkqueue*)malloc(sizeof(linkqueue)); q->front=(edgenode*)malloc(sizeof(edgenode)); q->front->next=NULL; q->rear=q->front; //printf("%d\n",s1); int visit[Max_len]; for(i=0;i<=n;i++) visit[i]=0; visit[s1]=1; ENQUEUEQ(q,s1); int find_t=0; for(i=0;i<=n;i++) pre_index[i]=-1; while(!EMPTY(q)){ i=DEQUEUEQ(q); int n_count=ga[i].num; s=ga[i].link; int q_count=0; while(q_count<n_count){ if(visit[s->adjvex]!=1){ pre_index[s->adjvex]=i; //printf("%d->%d\n",i,s->adjvex); if(s->adjvex==t){ find_t=1; goto next_1; } visit[s->adjvex]=1; ENQUEUEQ(q,s->adjvex); } s=s->next; q_count++; } } next_1: int find_triangle=0; if(find_t){ long triangle_num=0; long index=s->adjvex; while(index!=s1){ s=ga[pre_index[index]].link; int n_count=ga[pre_index[index]].num; int q_count=0; while(q_count<n_count){ if(s->adjvex==index) break; else s=s->next; q_count++; } triangle[triangle_num]=s->length; //printf("%d\n",s->length); triangle_num++; index=pre_index[index]; } if(triangle_num>2){ quick_sort(triangle,0,triangle_num-1); for(i=0;i<triangle_num;i++) for(j=i+1;j<triangle_num;j++) for(k=j+1;k<triangle_num;k++){ if(triangle[k]<triangle[i]+triangle[j]){find_triangle=1;break;} } } } if(find_triangle) printf("Yes\n"); else printf("No\n"); } } return 0; }