博文
PKU 3625(2009-11-24 19:51:00)
摘要：本题是 最小生成树，用prim 比较方便，用kruskal的话，我超时了，看了discuss 后才知道要用优先队列 优化。而且这题 prim 效率应该效率更高。
kruskal +优先队列
Memory: 8032K Time: 125MS Language: C++ Result: Accepted
#include<iostream>#include<cmath>#include<algorithm>using namespace std;int N,M,set[1021],need,num;double vx[1001],vy[1001];struct edge{ int x,y; double w;}e[555555];int find (int x){ int i,j,r; r=x; while(set[r]!=r) r=set[r]; j=x; while(j!=r) { i=set[j]; set[j]=r; j=i; } return r;}void merge(int x,int y){ if(x>y) set[x]=y; else set[y]=x;}void insert(edge a){ int i; num++; e[num]=a; i=num; while(i>1 &......
zoj 3010(2009-08-09 11:21:00)
摘要：DFS，规模很小，直接搜过#include<iostream>using namespace std;int n;double sum,m;bool mark[11],escape;struct vex{ int num,count[11]; double per;}a[12];void dfs(int si,int num,double max){ int total=0,i; double temp; if(num==n) { if(max>sum)sum=max; escape=1; return; } if(si==n+1)return; for( i=1;i<=a[si].num;i++) { if(mark[a[si].count[i]]){mark[a[si].count[i]]=0;total++;} else {mark[a[si].count[i]]=1;total--;} ......