Sweet Butter 香甜的黄油

　　　　题目大意：m个点，n头奶牛，p条边，每一头奶牛在一个点上，一个点可以有多只奶牛，求这样一个点，使得所有奶牛到这个点的距离之和最小。

　　　　注释：n<=500 , m<=800 , p<=1450 , 连边的牧场之间的距离d<=255

　　　　　　想法：显然，这是一个最短路问题，有两种途径：1. 跑多源最短路。2. 跑m遍单源最短路。

　　　　　　　　第1种想法想到floyd , 时间复杂度O(m^3)=O(5.12*10^8)，过不去，用第二种想法吧。

　　　　　　　　由于floyd都T了，n遍Dijkstra的时间复杂度也是O(m^3)，而另一种单源最短路是spfa，时间复杂度O(m*p+m*n)。所以，spfa才是我们想要的算法。

　　　　　　　　首先，对于每一个节点跑一遍spfa，注意清数组。存边用邻接矩阵或链式前向星均可，博主在此采用链式前向星。

　　　　最后，附上丑陋的代码...

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 using namespace std;

 queue<int>q;

 int f[],a[];

 bool v[];

 int to[],val[],next[],head[],tot;

 void add(int x,int y,int z)//存边

 {

     to[++tot]=y;

     val[tot]=z;

     next[tot]=head[x];

     head[x]=tot;

 }

 void spfa(int xp)//spfa,xp表示当前枚举的源点

 {

     memset(f,0x3f,sizeof(f));

     memset(v,,sizeof(v));

     q.push(xp),f[xp]=,v[xp]=;

     while(q.size())

     {

         int x,y;

         x=q.front(),q.pop(),v[x]=;

         for(int i=head[x];i;i=next[i])

         {

             if(f[y=to[i]]>f[x]+val[i])

             {

                 f[y]=f[x]+val[i];

                 if(v[y]==) q.push(y),v[y]=;

             }

         }

     }

 }

 int main()

 {

     int n,m,p;

     scanf("%d%d%d",&n,&m,&p);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

     }

     int fr,t,va;

     for(int i=;i<=p;i++)

     {

         scanf("%d%d%d",&fr,&t,&va);

         add(fr,t,va);//存双向边

         add(t,fr,va);//存双向边

     }

     long long minn=9220000000000000ll;

     for(int i=;i<=m;i++)

     {

         spfa(i);

         long long ans=;

         for(int j=;j<=n;j++)

         {

             ans+=f[a[j]];

         }

         minn=min(ans,minn);

     }

     printf("%lld",minn);

     return ;

 }

　　　　　　小结，错误

　　　　　　　　　　　　1.双向边，双向边，双向边

　　　　　　　　　　　　2.line 60：写成了 ans=min ( minn , ans ) 全盘爆蛋

　　　　　　　　　　　　3.因为本题不一定连通，所以在一定程度上我们需要考虑不连通的情况，所以ans和minn开long long 来解决。

　　转载请注明：http://www.cnblogs.com/ShuraK/p/7852461.html

巴特西

Sweet Butter 香甜的黄油

Sweet Butter 香甜的黄油

最新文章

热门文章