【日常学习】【Dijkstra堆优化】codevs2038 香甜的黄油题解

末蓝、 2022-08-04 16:44 204阅读 0赞

先放上题目，出自USACO

题目描述 Description

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场呆着（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入描述 Input Description

第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450).

第二行到第N+1行: 1到N头奶牛所在的牧场号.

第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然,连接是双向的.

输出描述 Output Description

一行 输出奶牛必须行走的最小的距离和.

样例输入 Sample Input

3 4 5
    2
    3
    4
    1 2 1
    1 3 5
    2 3 7
    2 4 3
    3 4 5

样例图形

P2  
    P1 @--1--@ C1
        \    |\
         \   | \
          5  7  3
           \ |   \
            \|    \ C3
          C2 @--5--@
             P3    P4

样例输出 Sample Output

{说明： 放在4号牧场最优. }

这道题目得耗了我二十多个小时 从最早的SPFA裸，到SLF和LLL优化，再到双结构体的可怜堆优化Dijkstra= =说起来都是泪啊TUT

根据朱全民在NOI导刊上的文章来看，此题最好的方法应该是SPFA

但是显然codevs加强了数据 边数剧增 导致SPFA退化到比裸的Dijkstra还慢  因为SPFA时间复杂度为O（km），m是边数，k期望为2，边数很大（比如这道题目n\*（n-1），n是点数）的情况下，比dij的O（n²）显然要慢。

正如我们之前总结过的，遇到稠密图，SPFA很是苦手。

加了两个优化，原理是把可以松弛的边放在队列前面，优先队列实现。但还是超时。如下

![Center][]

可以看出，随着数据规模增大，时间剧增，因为边数二次函数增长

而如果用优化的Dij，效果就要好得多。堆优化的原理是运用一个最小堆（c++可以通过STL的priority\_queue实现），使“查找dist最小边贪心”的复杂度降低到logn，而如果运用邻接表存储，直接查找能更新的点，更新dist的复杂度最大是n。因此堆优化后复杂度为O（nlogn），显然在稠密图中会大大降低时间复杂度。而相对于SPFA空间复杂度并没有增多很多（尤其是SPFA加了优化存储规模基本是一样的，也是写结构体+优先队列重载）。

我们来看一下dijkstra优化时间：

![SouthEast][]

显而易见，小数据差别并不大，dijkstra还要慢一些，而一旦数据规模爆表，dij优势不言而喻。大数据要快10倍。

接下来放上这几次尝试的代码吧

这是最原始的SPFA 裸的可以当模板

//codevs2038 USACO 香甜的黄油 SPFA 2T
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    int cow,v,e,a[801][801],c[501],in[801],dis[801],tot,ans;
    
    void init()
    {
    	memset(a,0x3f,sizeof(a));
    	memset(in,false,sizeof(in));
    	scanf("%d%d%d",&cow,&v,&e);
    	for (int i=1;i<=cow;i++) scanf("%d",&c[i]);
    	int x,y,z;
    	for (int i=1;i<=e;i++) {scanf("%d%d%d",&x,&y,&z);a[x][y]=z;a[y][x]=z;}
    	return;
    }
    
    void spfa(int &k)
    {
    	memset(dis,127,sizeof(dis));//127 is the largest plus number of memset
    	queue
          
            q;
    	q.push(k);
    	in[k]=true;
    	dis[k]=0;//don't forget
    	while (!q.empty())
    	{
    		int i=q.front();
    		in[i]=false;
    		q.pop();
    		for (int j=1;j<=v;j++)
    		{
    			if (dis[j]>dis[i]+a[i][j]) {dis[j]=dis[i]+a[i][j];in[j]=true;q.push(j);}
    		}
    	}
    	tot=0;
    	for (int i=1;i<=cow;i++) tot+=dis[c[i]];
    	return;
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	init();
    	ans=0x3f3f3f3f;
    	for (int i=1;i<=v;i++){spfa(i);if (tot

`SPFA还可以用SLF和LLL优化 两个优化本质是一样的，可以用结构体+重载小于号+优先队列实现 参见“玛丽卡” 接下来是原始版的dijkstra堆优化 和最终版区别是 元素一次性全部入队 每次最小元素出队并调整其他元素位置 这个程序WA了 但本身算法应该没有问题 我不想调试了所以先放到这里 请注意：这是 错误的程序 //codevs2038 香甜的黄油 重写 邻接表+dij堆优化
 //邻接表 优先队列 挑战 加油！
 #include             
 #include               
 #include                 
 using namespace std;
 
 int oo ;
 struct data
 {
 	int v,w,next;
 }e[3001];//edge 终点，边权，下一条同源边 
 
 struct w
 {
 	int dist,num;
 	bool operator < (w n2)const
 	{
 		return dist>n2.dist;
 	}             
 }node[801];//每个node是一个点，有编号和dist 
 
 int ne,n,p,c,a,b,d;
 int head[801],cow[801];//head:edge from here;cow:the position of each cow;
 bool vis[801];
 int tot,ans;
 
 void insert(int &x,int &y,int &w)
 {
 	ne++;
 	e[ne].v=y;
 	e[ne].w=w;
 	e[ne].next=head[x];
 	head[x]=ne;
 } 
 
 void init()
 {
 	scanf("%d%d%d",&n,&p,&c);
 	memset(head,0,sizeof(head));
 	for (int i=1;i<=n;i++) scanf("%d",&cow[i]);//from 1!
 	for (int i=1;i<=c;i++)
 	{
 		scanf("%d%d%d",&a,&b,&d);
 		insert(a,b,d);
 		insert(b,a,d);
 	}
 }
 
 void dij(int &k)
 {
 	priority_queue                    q;
 	node[k].dist=0;
 	for (int i=1;i<=p;i++) q.push(node[i]);
 	int disj,minj;//dis of j and number of j
 	for (int i=1;i<=p;i++)
 	{
 		minj=q.top().num;
 		disj=q.top().dist;
 		vis[minj]=true;
 		q.pop();
 	    int pi=head[minj];
 	    while (pi)
 	    {
 	    	if (!(vis[e[pi].v]) && (disj+e[pi].w < node[e[pi].v].dist || disj == oo))
 	    	    node[e[pi].v].dist=disj+e[pi].w;
 	    	pi=e[pi].next;
 		}
 	}
 	//首先循环一边找出dist最小的点
 	//然后循环一边对于每个点以dist为中间点更小就更新dist 
 	//从当前dist连着的边里找 
 	tot=0;
 	for (int i=1;i<=n;i++) tot+=node[cow[i]].dist;//结果反馈：与K直接连着的边正常，不直接相连的正无穷未更新 
 	return;
 }
 
 int main()
 {
 	freopen("1.txt","r",stdin);
 	int inf = 0x3f3f3f;
 	oo = inf;
 	init();
 	ans=0x3f3f3f3f;
 	for (int i=1;i<=p;i++) node[i].num=i;
 	for (int i=1;i<=p;i++)
 	{
 		memset(vis,false,sizeof(vis));
 		for (int j=1;j<=p;j++) 
 		{
 		    node[j].dist=0x3f3f3f;
 		}
 	    dij(i);if (tot                                        接下来是最终版 像bfs那样 每次扩展出新的节点入队  //codevs2038 香甜的黄油 重写 邻接表+dij堆优化
 //邻接表 优先队列 挑战 加油！
 #include                 
 #include                   
 #include                     
 using namespace std;
 
 int oo ;
 struct data
 {
 	int v,w,next;
 }e[3001];//edge 终点，边权，下一条同源边 
 
 struct w
 {
 	int dist,num;
 	bool operator < (w n2)const
 	{
 		return dist>n2.dist;
 	}             
 }node[801];//每个node是一个点，有编号和dist 
 
 int ne,n,p,c,a,b,d;
 int head[801],cow[801];//head:edge from here;cow:the position of each cow;
 bool vis[801];
 int tot,ans;
 
 void insert(int &x,int &y,int &w)
 {
 	ne++;
 	e[ne].v=y;
 	e[ne].w=w;
 	e[ne].next=head[x];
 	head[x]=ne;
 } 
 
 void init()
 {
 	scanf("%d%d%d",&n,&p,&c);
 	memset(head,0,sizeof(head));
 	for (int i=1;i<=n;i++) scanf("%d",&cow[i]);//from 1!
 	for (int i=1;i<=c;i++)
 	{
 		scanf("%d%d%d",&a,&b,&d);
 		insert(a,b,d);
 		insert(b,a,d);
 	}
 }
 
 void dij(int &k)
 {
 	priority_queue                        q;
 	node[k].dist=0;
 	q.push(node[k]);
 	int disj,minj;//dis of j and number of j
 	while (!q.empty()) 
 	{
 		minj=q.top().num;
 		disj=q.top().dist;
 		vis[minj]=true;
 		q.pop();
 	    int pi=head[minj];
 	    while (pi)
 	    {
 	    	if (!(vis[e[pi].v]) && (disj+e[pi].w < node[e[pi].v].dist || disj == oo))
 	    	    {node[e[pi].v].dist=disj+e[pi].w;q.push(node[e[pi].v]);}
 	    	pi=e[pi].next;
 		}
 	}
 	//首先循环一边找出dist最小的点
 	//然后循环一边对于每个点以dist为中间点更小就更新dist 
 	//从当前dist连着的边里找 
 	tot=0;
 	for (int i=1;i<=n;i++) tot+=node[cow[i]].dist;//结果反馈：与K直接连着的边正常，不直接相连的正无穷未更新 
 	return;
 }
 
 int main()
 {
 	freopen("1.txt","r",stdin);
 	int inf = 0x3f3f3f3f;
 	oo = inf;
 	init();
 	ans=0x3f3f3f3f;
 	for (int i=1;i<=p;i++) node[i].num=i;
 	for (int i=1;i<=p;i++)
 	{
 		memset(vis,false,sizeof(vis));
 		for (int j=1;j<=p;j++) 
 		{
 		    node[j].dist=0x3f3f3f;
 		}
 	    dij(i);if (tot                                                  另外，方便pascal同学们，最后附上朱全民老师pascal代码对这个题目的讲解。但是请注意，朱全民老师讲解用的是USACO原始数据，是稀疏图，最优解SPFA ——一叶扁舟轻帆卷，暂泊楚江南岸。`

[http_blog.csdn.net_ametake]: http://blog.csdn.net/ametake
[Center]: /images/20220805/956d51b72a6649faad03cb70ffde047e.png
[SouthEast]: /images/20220805/0f09d08bffcd457da0f2364de5186796.png