USACO chapter 3 section 2 Sweet Butter

做了一题,开心,冒一下泡:
题目大意:有一些草原(1,……,p个),告诉你n个奶牛的在哪个草原,Famer John 会在其中一个草原放一块糖,
让所有的奶牛去舔(提高奶的质量^-^),要求的就是把糖放在哪个草原使所有的奶牛到那的路程和最短。
(当然奶牛都是拣最短的路走)。
 
第一种超时思路 :Floyd算法求出任意两个草原间的距离,枚举所有草原,取所有奶牛所在的草原到该草原和的最大值。
               很不幸TLE了,O(800^3);
第二种超时思路:用Dijkstra+priority_queue(优先级队列),枚举所有草原算单源最短路径,如果不优化还是O(800^3)
用priority_queue还是TLE了,Dijkstra找最近的的时候用优先级队列很快,O(1),调整O(log n),可能是用的不够好。
貌似有人用这种方法做出来。不知道用邻接表行不行。
 
第三种思路:就是SPFA算法(Shortest Path Fast Algorithm):
用邻接表,枚举所有草原,用SPFA算单源最短路径,SPFA算法要用到队列,一个标记数组用于判断是否在队列中,
d[]数组,存放i到所有点的距离,初始值都为MAX,d[i]=0。
枚举的草原i先入队。如果队列非空就开始迭代,取队首元素x并弹出它,对于所有与x相邻的(邻接表的好处体现了)u,
如果d[u]>d[x]+len(x,u)(x到u的距离)d[u]=d[x]+len(x,u),这样d[u]进行更新了,d[u]可能会继续更新别的点,
如果u不在队列的话,就把u放在队列中。一直迭代下去,直到队列为空(就是说没有在更新了);
 

1# TLE
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 5544 KB]
Test 2: TEST OK [0.000 secs, 5544 KB]
Test 3: TEST OK [0.011 secs, 5544 KB]
Test 4: TEST OK [0.022 secs, 5544 KB]
Test 5: TEST OK [0.022 secs, 5544 KB]
Test 6: TEST OK [0.054 secs, 5544 KB]
Test 7: TEST OK [0.410 secs, 5544 KB]
  > Run 8: Execution error: Your program (`butter') used more than the
            allotted runtime of 1 seconds (it ended or was stopped at 1.339
            seconds) when presented with test case 8. It used 5544 KB of
            memory.
            

想用Foloyd()求最短路径,超时了。
/*
ID:tbbd4261
PROG:butter
LANG:C++
*/

#include
<fstream>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
int adj[MAX][MAX]={0};
int location[505];
int n,p,c;
ifstream fin(
"butter.in");
ofstream fout(
"butter.out");
void init()
{
     
int i,j;
     
for(i=1; i<=p; i++)
     
for(j=1; j<=p; j++)
         adj[i][j]
=INF;
     
for(i=1; i<=p; i++)
              adj[i][i]
=0;
}

void Floyd()
{
     
int i,j,k;
     
for(k=1; k<=p; k++)
      
for(i=1; i<=p; i++)
       
for(j=1; j<=p; j++)
       {
        
if(i==j)continue;
        
if(adj[i][j]>adj[i][k]+adj[k][j])
                  adj[i][j]
=adj[i][k]+adj[k][j];     
       }
}

void print()
{
      
int i,j;
     
for(i=1; i<=p; i++,fout<<endl)
     
for(j=1; j<=p; j++)
              fout
<<adj[i][j]<<' ';
}

int main()
{
    
    fin
>>n>>p>>c;
    init();
  
    
for(int i=1; i<=n; i++ )
         fin
>>location[i];
    
    
for(int i=1,len,s,t; i<=c; i++)
    {
            fin
>>s>>t>>len;
            adj[t][s]
=adj[s][t]=len;
    }
    Floyd();
    
int minSum=INF,sum;
    
for(int i=1; i<=p; i++)
    {
            
bool f=true;
            sum
=0;
            
for(int j=1; j<=n; j++)
            {
                    
if(adj[i][location[j]]!=INF)
                    {
                       sum
+=adj[i][location[j]];
                    }
                    
else f=false
            }
            
if(f==true&&sum<minSum)minSum=sum;
                              
    }
    
    fout
<<minSum<<endl;
    
    
return 0;
}
2,TLE
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 5552 KB]
Test 2: TEST OK [0.022 secs, 5552 KB]
Test 3: TEST OK [0.011 secs, 5552 KB]
Test 4: TEST OK [0.011 secs, 5552 KB]
Test 5: TEST OK [0.032 secs, 5552 KB]
Test 6: TEST OK [0.097 secs, 5552 KB]
Test 7: TEST OK [0.637 secs, 5552 KB]
  > Run 8: Execution error: Your program (`butter') used more than the
            allotted runtime of 1 seconds (it ended or was stopped at 1.674
            seconds) when presented with test case 8. It used 5552 KB of
            memory.
            
 改用Dijkstra+priority_queue(STL)更慢了…………

 

/*
ID:tbbd4261
PROG:butter
LANG:C++
*/

#include
<fstream>
#include
<iostream>
#include
<queue>
#include
<functional>
#include
<cstring>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
int n,p,c;
int location[505]={0};
int adj[MAX][MAX]={0};
ifstream fin(
"butter.in");
ofstream fout(
"butter.out");

typedef pair
<int ,int > type;

int d[MAX];
bool done[MAX];
int dijkstra(int t)
{
    memset(done,
0,sizeof done);
    
for(int i=1; i<=p; i++)
            d[i]
=INF;
    d[t]
=0;
    priority_queue
<int ,vector<type > ,greater<type> >q;
    q.push(make_pair(d[t],t));
    type temp;
    
while(!q.empty())
    {
            temp
=q.top();  q.pop();
            
int x=temp.second;
            
if(done[x])continue;
            done[x]
=true;
            
//fout<<x<<' '<<d[x]<<endl;
            for(int j=1; j<=p; j++)
            {
                    
if(d[j]>d[x]+adj[x][j])
                          {
                             d[j]
=d[x]+adj[x][j];
                             q.push(make_pair(d[j],j));
                          }
            }
    }
    
int ans=0;
    
for(int i=1; i<=n; i++)
            
if(d[location[i]]==INF)return -1;
            
else ans+=d[location[i]];  
    
return  ans;
}

void init()
{
     
int i,j;
     
for(i=1; i<=p; i++)
     
for(j=1; j<=p; j++)
          adj[i][j]
=(i==j?0:INF);    
}

void print()
{
     fout
<<"print location: "<<endl;
     
for(int i=1; i<=n; i++)
             fout
<<location[i]<<' ';
     fout
<<endl;
     fout
<<"print adj: "<<endl;
     
for(int i=1; i<=p; i++,fout<<endl)
     
for(int j=1; j<=p; j++)
             fout
<<adj[i][j]<<' ';
     fout
<<endl;
}
int main()
{
    fin
>>n>>p>>c;
    init();
    
for(int i=1; i<=n; i++)
            fin
>>location[i];
            
    
for(int i=1,s,t,len; i<=c; i++)
    {
            fin
>>s>>t>>len;
            adj[s][t]
=adj[t][s]=len;
    }
    
//print();
    int min=INF;
    
for(int i=1,tt; i<=p; i++)
    {
             tt
= dijkstra(i);
             
//system("pause");
             if(tt!=-1&&tt<min)
                       min
=tt;
    }
    fout
<<min<<endl;
    
//system("pause");
    return 0;
}
USER: tian tianbing [tbbd4261]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 8084 KB]
Test 2: TEST OK [0.000 secs, 8084 KB]
Test 3: TEST OK [0.011 secs, 8084 KB]
Test 4: TEST OK [0.022 secs, 8084 KB]
Test 5: TEST OK [0.000 secs, 8084 KB]
Test 6: TEST OK [0.011 secs, 8084 KB]
Test 7: TEST OK [0.054 secs, 8084 KB]
Test 8: TEST OK [0.108 secs, 8084 KB]
Test 9: TEST OK [0.162 secs, 8084 KB]
Test 10: TEST OK [0.173 secs, 8084 KB]
All tests OK.

Your program ('butter') produced all correct answers! This is your submission #5 for this problem. Congratulations!


3,A了!
千呼万唤始出来,终于A了,而且速度挺快!!!
传说中的SPFA算法:
 
/*
ID:tbbd4261
PROG:butter
LANG:C++
*/

#include
<fstream>
#include
<cstring>
#include
<queue>
using namespace std;
const int MAX=805;
const int INF=0x0fffffff;
ifstream fin(
"butter.in");
ofstream fout(
"butter.out");
struct node{
       
int end,len;
};
int cnt[MAX]={0},location[505]={0},n,p,c;
node adj[MAX][MAX];
bool in[MAX]={0};
int d[MAX];
int SPFA(int i)
{
    memset(
in,0,sizeof in);
    
for(int k=1; k<=p; k++)d[k]=INF;
    queue
<int> Q;
    Q.push(i); 
    
in[i]=true;
    d[i]
=0;
    
while(!Q.empty())
    {
          
int x=Q.front(); Q.pop();
          
in[x]=false;
          
for(int j=0; j<cnt[x]; j++)
                  
if(d[x]+adj[x][j].len < d[ adj[x][j].end ])
                  {
                   d[adj[x][j].end]
=d[x]+adj[x][j].len;   
                   
if(!in[adj[x][j].end])
                                        { 
                                        Q.push(adj[x][j].end);
                                        
in[adj[x][j].end ]=true
                                        }                      
                  }
    }
    
    
int ans=0;
    
    
for(int j=1; j<=n; j++)
    {
            
if(d[location[j]]==INF)return -1
            
else  ans+=d[location[j]]; 
    }
    
return ans;
}

void print()
{
     
int i,j;
     
for(i=1; i<=p ; i++)
     
for(j=0; j<cnt[i]; j++)
     {
              fout
<<i<<' '<<adj[i][j].end<<' '<<adj[i][j].len<<endl;
     }
}

int main()
{
    memset(cnt,
0,sizeof cnt);
    fin
>>n>>p>>c;
    
for(int i=1; i<=n; i++)
            fin
>>location[i];
    
    
for(int i=1,s,t,value; i<=c; i++)
    {
            fin
>>s>>t>>value;
            adj[s][cnt[s]].end
=t; adj[s][cnt[s]].len=value; cnt[s]++;
            adj[t][cnt[t]].end
=s; adj[t][cnt[t]].len=value; cnt[t]++;
    }
    
    
int tt,min=INF;
    
    
for(int i=1; i<=p; i++)
    {
            tt
=SPFA(i); 
            
if(tt<min&&tt!=-1) min=tt;
    }
    fout
<<min<<endl;
    
//system("pause");
    return 0;
}

posted on 2010-08-08 09:20 田兵 阅读(1693) 评论(7)  编辑 收藏 引用 所属分类: 算法笔记USACO

评论

# re: USACO chapter 3 section 2 Sweet Butter[未登录] 2010-08-10 16:34 Klion

楼主你第二种方法应该是用优先队列引起的,自己手写堆试试,应该可以达到和spfa差不多的效果  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter 2010-08-10 21:33 田兵

@Klion
为什么用优先级队列就变慢了,第三种方法里还用了队列还那么快?

难道是因为大量元素移动?

  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter[未登录] 2010-08-10 23:49 Klion

@田兵
这个应该是stl的一个比较不爽的地方吧,stl确实很方便,不过有时确实用优先队列会超时,但是自己手写堆可过,这个应该和stl的实现有关,具体的我也不是很清楚(标称是手写heap+dij最后那组数据也只有0.2S)。第三种还那么快应该是因为spfa快吧。  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter[未登录] 2010-08-10 23:54 Klion

发现你刷usaco好快啊,我最近也在刷usaco,可以交个朋友么?
QQ:978132955
Email:qcx978132955@yeah.net  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter 2010-08-11 08:53 田兵

@Klion
哦 谢谢,stl的确是有点慢,对大量数据时很不爽,一般如果容器内存不够时它会重新分配一个容量是现在的两倍。  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter 2010-08-11 08:58 田兵

@Klion

谈不上刷,我们学校暑假做这个,很多都是参考NOCOW上的,当然可以交朋友,有问题我可以请教你了,我QQ346523942。^-^  回复  更多评论   

# re: USACO chapter 3 section 2 Sweet Butter 2011-01-22 21:19 st8676746

我是用STL的优先队列+Dijkstra过的~而且貌似不比你的SPFA慢~所以你可以检查一下你的heap版本的Dijkstra是否写错了?
注意用堆优化的Dijkstra必须用邻接表,否则复杂度无法降低(甚至更慢)。  回复  更多评论   


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


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜