博文
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[......
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++;}
&n......