http://202.120.80.191/problem.php?problemid=2104
這道題是最短路的變形，只要修改下狀態(tài)方程，如果用最短路用堆優(yōu)化,dist同樣是每次都要更新
dist[tmp->v]=max(dist[tmp->v],min(dist[it],tmp->w));
我用stl的堆，但是一直出問題，所以能不能幫我看下一下問題是怎么出的
#include<iostream>
#include<algorithm>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
#define MaxM 1000005
#define MaxN 100005
#define MaxW 2000000005
int dist[MaxN];//dist上存儲的是擴(kuò)展當(dāng)前這個(gè)點(diǎn)是的可攜帶的最大負(fù)重
struct node
{
int v,w;
node *next;
node()
{
w=v=0;next=0;}
};
node *V[MaxN];
int flag[MaxN];
int heap[2*MaxN],hsize;
int N,M;
bool cmp(int a,int b)
{
return dist[a]<dist[b];
}
void solve(int s,int t)
{
int it,i;
node *tmp;
dist[s]=MaxW;
hsize=1;
heap[0]=s;
make_heap(heap,heap+hsize,cmp);
while(!flag[t]){
if(!hsize)break;
it=heap[0];
pop_heap(heap,heap+hsize);
hsize--;
if(flag[it]==1)continue;
flag[it]=1;
for(tmp=V[it];tmp!=0;tmp=tmp->next)
if(!flag[tmp->v]){
dist[tmp->v]=max(dist[tmp->v],min(dist[it],tmp->w));//更新dist的值
heap[hsize++]=tmp->v;
push_heap(heap,heap+hsize,cmp);}
make_heap(heap,heap+hsize,cmp);//按理說這里是不用make_heap的
//因?yàn)樵谏厦嬉恍兄衟ush_heap會(huì)調(diào)整堆，但是我這個(gè)程序就是不行，我實(shí)在不知道問什么，push_heap能插入，但是并沒
//實(shí)現(xiàn)最大堆，逼得我沒辦法要加上個(gè)重新建堆，但是加上這個(gè)后速度爆滿，本來這個(gè)寫法只能勉強(qiáng)過，我加上他后只能超時(shí)了，希望高人指點(diǎn)，為什么我這里堆的使用就是會(huì)出現(xiàn)這種問題
}
printf("%d\n",dist[t]);
}
void delete_V(node* p)
{
if(p==NULL)return;
delete_V(p->next);
delete(p);
}
int main()
{
int u,v,w,s,t,i;
node *tmp;
while(scanf("%d%d",&N,&M)!=EOF&&N&&M){
memset(heap,0,sizeof(heap));
memset(dist,0,sizeof(dist));
memset(flag,0,sizeof(flag));
memset(V,0,sizeof(V));
for(i=0;i<M;i++){
scanf("%d%d%d",&u,&v,&w);
tmp=(node*)malloc(sizeof(node));
tmp->v=v; tmp->w=w; tmp->next=V[u]; V[u]=tmp;
tmp=(node*)malloc(sizeof(node));
tmp->v=u; tmp->w=w; tmp->next=V[v]; V[v]=tmp;
}
scanf("%d%d",&s,&t);
solve(s,t);
for(i=1;i<=N;i++)
delete_V(V[i]);
}
return 0;
}后面實(shí)在沒辦法，該并查集的做法，用并查集確實(shí)簡單很多，以下是我的代碼
#include<iostream>
#include<algorithm>
#define MaxM 1000005
#define MaxN 100005
using namespace std;
struct eNode
{
int begin,end,w;
}E[MaxM];
struct node
{
int parent,rank;
}V[MaxN];
int N,M;
bool cmp(eNode a,eNode b)
{
return a.w>b.w;
}
void make_set()
{
for(int i=1;i<=N;i++){ V[i].parent=i; V[i].rank=0;}
}
int find(int i)
{
if(V[i].parent!=i)
return V[i].parent=find(V[i].parent);
else return i;
}
void union_set(int a,int b)
{
int fa,fb;
fa=find(a); fb=find(b);
if(V[fa].rank<V[fb].rank)V[fa].parent=fb;
else {
V[fb].parent=fa;
if(V[fa].rank==V[fb].rank)++V[fa].rank;
}
}
void solve(int s,int t)
{
int i,u,v;
make_set();
for(i=0;i<M;i++){
u=E[i].begin; v=E[i].end;
if(find(u)==find(v))continue;
union_set(u,v);
if(find(s)==find(t)){
printf("%d\n",E[i].w);
return;}
}
}
int main()
{
int i,u,v,w,s,t;
while(scanf("%d%d",&N,&M)!=EOF){
memset(E,0,sizeof(E));
for(i=0;i<M;i++){
scanf("%d%d%d",&u,&v,&w);
E[i].begin=u; E[i].end=v; E[i].w=w;
}
sort(E,E+M,cmp);
scanf("%d%d",&s,&t);
solve(s,t);
}
return 0;
}
posted on 2008-04-29 19:17
zoyi 閱讀(256)
評論(1) 編輯 收藏 引用 所屬分類:
acm 、
數(shù)據(jù)結(jié)構(gòu)