infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=3159

比较变态的题目,还是sempr大牛出的题^-^!!
我只用spfa 踩点1500ms过了!用 dijkstra+heap TLE了!不知道是不是自己写的有问题?

题目意思:
flymouse是幼稚园班上的班长,一天老师给小朋友们买了一堆的糖果,由flymouse来分发,在班上,
flymouse和snoopy是死对头,两人势如水火,不能相容,因此fly希望自己分得的糖果数尽量多于
snoopy,而对于其他小朋友而言,则只希望自己得到的糖果不少于班上某某其他人就行了。

比如A小朋友强烈希望自己的糖果数不能少于B小朋友m个,即B- A<=m,A,B分别为
A、B小朋友的分得的糖果数。这样给出若干组这样的条件,要使fly最后分得的糖果数s1和snoopy
最后分得的糖果数s2差别取到最大!即s2-s1取最大.

因此根据题意,可以列出如下的不等式:
  
    Sbi-Sai<=ci(1=<i<=n)             
  
最终要使得Sn-S1最大;

其实就是一个差分约束系统。
求最短路时用到的三角形不等式中,最终对于每条有向边(u,v)有: d[v]<=d[u]+w(u,v);
将Sbi-Sai<=ci变成Sbi<=Sai+ci;就跟上式的形式相似。

在最短路的松弛过程中每次都是 if(d[v]>d[u]+w(u,v)) then d[v]<=d[u]+w(u,v);
则最后不断的松弛,使得对所有边 d[v]<=d[u]+w(u,v);
对于Sbi<=Sai+ci;通过做bellmanford,Sbi通过不断的松弛,由正的无穷不断减小,直到所有的
约束条件都的到满足,所以这时的求出的Sbi是满足约束条件的最大的一组解!!
这样最后的结果就是Sn-S1,初始时将S1设为0,则最后的结果就是Sn的值!
不过直接用bellman-ford复杂度高了点!用队列优化的bellman-ford即spfa可以承受!

代码写起来比较简洁

Source Code

Problem: 3159
User: lovecanon
Memory: 6972K
Time: 1500MS
Language: C++
Result: Accepted


 
#include<stdio.h>
#include
<string.h>
struct node{
    
int v,val;
    node 
*next;
}edge[
150001];
int n,m,dist[30001],mem[30001],s[30001],top;

void insert(int a,int b,int c){
    node 
*s=new node;
    s
->v=b;s->val=c;
    s
->next=edge[a].next;
    edge[a].next
=s;
}
void spfa(){
    memset(s,
0,sizeof(s));
    top
=0;
    mem[
++top]=1;
    memset(dist,
127,sizeof(dist));
    dist[
1]=0;
    s[
1]=1;
    
while(top){
        
int cnt=mem[top--];
        s[cnt]
=0;
        node 
*ptr=edge[cnt].next;
        
while(ptr){
            
int tmp=ptr->v;
            
if(dist[tmp]>dist[cnt]+ptr->val){
                dist[tmp]
=dist[cnt]+ptr->val;
                
if(!s[tmp]){
                    mem[
++top]=tmp;
                    s[tmp]
=1;
                }
            }
            ptr
=ptr->next;
        }
    }
    printf(
"%d\n",dist[n]);
}
int main(){
    
int i,a,b,c;
    
while(scanf("%d%d",&n,&m)!=EOF){
        memset(edge,
0,sizeof(edge));
        
for(i=1;i<=m;i++){
            scanf(
"%d%d%d",&a,&b,&c);
            insert(a,b,c);
        }
        spfa();
    }
    
}



另外附上我写的heap+dijkstra,总是超时,实在无语,望哪位路过的大牛指点迷津!!



#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
struct node{
    
int v,val;
    node 
*next;
}edge[
150001];
struct Heap{
    
int v,val;
}heap[
30001];
int n,m,dist[30001],s[30001],tail;

int get_min(int a,int b){if(a<=b) return a;else return b;}

void insert(int a,int b,int c){
    node 
*s=new node;
    s
->v=b;s->val=c;
    s
->next=edge[a].next;
    edge[a].next
=s;
}

void heap_push(int v,int val){
    heap[
++tail].v=v;heap[tail].val=val;
    
int root=tail;
    
while(root/2){
        
if(heap[root/2].val>heap[root].val){
            
int tmp1,tmp2;
            tmp1
=heap[root].v;tmp2=heap[root].val;
            heap[root].v
=heap[root/2].v;heap[root].val=heap[root/2].val;
            heap[root
/2].v=tmp1;heap[root/2].val=tmp2;
        }
        root
/=2;
    }
}

int heap_pop(){
    
int res=heap[1].v;
    heap[
1].v=heap[tail].v;heap[1].val=heap[tail--].val;
    
int root=1,pos;
    
while((pos=root*2)<=tail){
        
if(pos+1<=tail&&heap[pos+1].val<heap[pos].val) pos++;    
        
if(heap[root].val<heap[pos].val){
            
int tmp1,tmp2;
            tmp1
=heap[root].v;tmp2=heap[root].val;
            heap[root].v
=heap[pos].v;heap[root].val=heap[pos].val;
            heap[pos].v
=tmp1;heap[pos].val=tmp2;
            root
=pos;
        }
    } 
    
return res;
}

void dijkstra(){
    memset(dist,
127,sizeof(dist));
    memset(s,
0,sizeof(s));
    dist[
1]=0;
    s[
1]=1;
    tail
=0;
    heap_push(
1,0);
    
while(tail){
        
int cnt=heap_pop(),id;
        
if(cnt==n) break;
        s[cnt]
=1;
        node 
*ptr=edge[cnt].next;
        
while(ptr && !s[ptr->v]){
            
if(dist[ptr->v]>dist[cnt]+ptr->val){
                dist[ptr
->v]=dist[cnt]+ptr->val;
                heap_push(ptr
->v,dist[ptr->v]);
            }
            ptr
=ptr->next;
        }
    }
    printf(
"%d\n",dist[n]);
}

int main(){
    
while(scanf("%d%d",&n,&m)!=EOF){
        memset(edge,
0,sizeof(edge));
        
//memset(heap,127,sizeof(heap));
        int i,a,b,c;
        
for(i=1;i<=m;i++){
            scanf(
"%d%d%d",&a,&b,&c);
            insert(a,b,c);
        }
        dijkstra();
    }
    
return 0;
    
}




posted on 2008-11-05 17:37 infinity 阅读(1267) 评论(1)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 3159 Candies 2011-03-10 22:08 saintqdd
用队列优化的belllman_ford一直超时,换用堆过了。不过比博主的快了很多500+ms  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理