第十二周总结

本周学习了最小生成树，以下几个题为比较典型的题目

大体题意：每次去一个点后并返回，求到达每个点并返回的最短距离

 做这个题目思路很简单，做的时候自己想的是用邻接表，把每个点正反的最短用Ford求出来然后再去每个相加判断，不过看了题解发现其实用一个数组也可以，交换的话更省时间和代码，具体代码如下

#include
using namespace std;
const int INF=100000000;
int n,m;
int u[100010],v[100010],w[100010];// u起点，v终点，w长度
int dis[1010];
void over()
{
    for(int i=1; i<=m; i++)
    {
        swap(u[i],v[i]);
    }
}
void ford()
{
    for(int i=1; i<=n; i++)dis[i]=INF;
    dis[1]=0;
    for(int k=1; k<=n-1; k++)
    {
        for(int i=1; i<=m; i++)
        {
            if(dis[v[i]]>dis[u[i]]+w[i])
            {
                dis[v[i]]=dis[u[i]]+w[i];
            }
        }
    }
}
int main()
{


    cin>>n>>m;
    for(int i=1; i<=m; i++)
    cin>>u[i]>>v[i]>>w[i];
    long long  ans=0;
    ford();
    for(int i=1; i<=n; i++)ans+=dis[i]; //从一到多
    over();//反转，反向建边
    ford();//跑最短路
    for(int i=1; i<=n; i++)ans+=dis[i]; //从多到一
    cout<

大体题意：给出每个区域之间的距离，求从1走完所以有宝藏的位置，求路最短距离 

做这个题组里面的题目时自主的想到肯定就是用那几种最小生成树的算法和常规的几种图论处理，因为时间复杂度更低吗，或者就是更省代码，但是，开始做这个题目的时候权值吗，最小吗，想到的还找其中一个算法来解决，而且数据也不大那么就用ford呗，但是后来发现数据不好处理，好像邻接表，向量，数组都处理不了这个数据，那么就来到了深搜，用深搜先确定所有点的最小值然后再用ford处理邻近最短的数据，代码如下：

#include
using namespace std;
#define r(x,a,b) for(int x=a;x>n;
    r(i,1,n+1)
    r(j,1,n+1)
    cin>>t[i][j];
    cin>>m;
    for(int i=1; i<=m; i++)
        cin>>k[i];

    for(int k=1; k<=n; k++)

    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                if(i!=j!=k)
                    t[i][j]=min(t[i][j],t[i][k]+t[k][j]);
        }
    }
    dfs(1,m,0);
    cout<

 这两个题基本上都是floyd的模板题

第一个题为例，大体题意为：给出每路的最高栏求n到m最高栏高度最低

思路也很简单，而且数据不是很大，就要数组，这个不是使栏最大值最低吗，那就把某段线段的去最值换成栏最大然后取小呗（动态规划方程）也就是Floyd的核心，然后输出每个点就ok了，代码如下。

#include
#define inf 336860180
using namespace std;
int T,s,t,n,m,d[400][400];
int main()
{
    memset(d,20,sizeof(d));
    cin>>n>>m>>T;
    for(int i=1;i<=m;i++)
    {
     int x,y,h;cin>>x>>y>>h;
      d[x][y]=h;
    }
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       d[i][j]=min(max(d[i][k],d[k][j]),d[i][j]);//DP动态转移方程
    for(int i=1;i<=T;i++)
    {
      int x,y;
      cin>>x>>y;
      if(d[x][y]!=inf) cout< 
 
 
[USACO09OPEN]Hide and Seek S - 洛谷
大体题意：求距离低一点最远的点位置，长度，有多少个距离一样
 
那么带权，数据不大，那就还是ford，由于是双向的所有建图时需要建两次，然后每个相邻的点之间距离为在ford模板里面1每次加一就好了，最后找到最大值输出就好了
 
#include
using namespace std;
int n,m,x,y;
int ver[100000+10],next1[100000+10],head[20000+10],tot=1;
bool v[100000+10];
int d[100000+10];
int q[111111],l=1,r;
void add(int x,int y)//邻接表
{
 ver[++tot]=y;
 next1[tot]=head[x];
 head[x]=tot;
}
void FORd()
{
 q[++r]=1;
 memset(d,0x3f,sizeof d);
 d[1]=0;
 while(l<=r)
 {
  int x=q[l++];
  v[x]=0;
  for(int i=head[x];i;i=next1[i])
  {
   int y=ver[i];
   if(d[y]>d[x]+1)
   {
    d[y]=d[x]+1;
    if(!v[y])q[++r]=y,v[y]=1;
   }
  }
 }
}
int main()
{
 cin>>n>>m;
 while(m--)
 {
  cin>>x>>y;
  add(x,y);
  add(y,x);
 }
 FORd();
 int ans1=0,ans2=0,ans3=0;

 for(int i=1;i<=n;i++)
 ans1=max(ans1,d[i]);
 for(int i=1;i<=n;i++)
 if(d[i]==ans1)
 {
  if(!ans2)
  ans2=i;
  ans3++;
 }
 cout<
 
[USACO10FEB]Chocolate Giving S - 洛谷
大体题意：给出双向路径，求某点到1点后，再到另一点的最短路
 
要是用Ford，floyd能求出结果但是呢会超时，所有你就只能用这个最长的dijkstra了，先用vector存一下图，然后就写优先队列，每次取两个，然后符合往里面压,最后输入所求的点，之间输出答案即可，说起来可轻松了，调起程序来哎
 
#include
using namespace std;
int n,m,t,d[50000+10],ans;
struct edge
{
 int to,cost;
};
vectorG[50010];//vector存图
typedef pairP;
void dijkstra(int s)
{
 priority_queue,greater
 >q;
 for(int i=1;i<=n;i++) d[i]=10e8;
 d[s]=0;
 q.push(P{0,s});
 while(!q.empty())
 {
  P p=q.top();//取队首
  q.pop();

  int v=p.second;
  if(d[v]d[v]+e.cost)//松弛
   {
    d[e.to]=d[v]+e.cost;
    q.push(P{d[e.to],e.to});
   }
  }
 }
}
int main()
{
 cin>>n>>m>>t;
 while(m--)
 {
  int u,v,w;
  cin>>u>>v>>w;
  G[u].push_back(edge{v,w});
  G[v].push_back(edge{u,w});
 }
 dijkstra(1);
 while(t--)
 {
  ans=0;
  int u,v;
  cin>>u>>v;
  ans=d[u]+d[v];
  cout<
 
总结：处理数据不是很大的情况下用ford（spfa）或者floyd（但是时间复杂度高）比较好用因为毕竟省代码吗，写的东西比较少，但是在数据时要确定用数组，还是邻接表，在一些数据类型比较大的题目里面一般要用dijkstra，当然就论时间复杂度来说的话，dijkstra要好一些，但是我个人不喜欢，因为写的东西太多了出错的机会就多了，上面那个个dijkstra的题解我看的调的里面最短的，与ford，floyd相比实在太长了，想这类生成树的题目，都比较固定模板化，就是确定用floyd，ford还是dijkstra，处理数据是向量，数组还是邻接表。