今天是九月三十号，国庆长假的前一天。我的国庆是注定要悲剧了，撬了一个半星期的课到时候还要补，我撬课一方面是想体验下不同的学习方式，另一方面主要还是希望准备10月三日的武汉赛，不过两个星期肯定是没有质的变化的，但是还是想体验下。我觉得呢，做ACM就像是做一项事业，总需要百分百的投入一段时间拼一下。

看了两天数论实在看不下去了，到舞房练了一下午的舞，

这个就不多说了……

#include<iostream>
using namespace std;

void floyd(int** a,int** path,int n){
int i,j,k;
for(k=1;k<=n;k++)    //Floyd
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
     if ( a[i][k] == 1000000 || a[k][j] == 1000000 ) continue;
     if ( a[i][k]+a[k][j] < a[i][j] ){
      a[i][j]=a[i][k]+a[

#include<iostream>
#include<queue>
using namespace std;

bool SPFA(int** map,int n){
int i,j,k;
for(i=1;i<=n;i++){   //source i
   queue<int> q;
   int dist[600];
   bool inqueue[600];
   memset(dist,1000000,sizeof(dist));
   memset(inqueue,true,sizeof(inqueue));
   dist[i]=0;
   q.push(i);
   inqueue[i]=true;

该程序还有改进空间，网上说最优化的Dijkstra是用heap实现，不过还没找到模板，最近会自己编一下。

#include <iostream>
using namespace std;

struct node
{
int weight;
int point;
node()
{
   weight = 0;
   point = 0;
}
node(int out_weight, int out_point)
{
   weight = out_weight;
   point = out_point;
}

};

int main()
{
int i;
int m;

一段时间以来的总结

zjj

heap的常用操作可以使用stl的四种函数实现

1. 头文件如下

#include <iostream>
#include <vector>
#include <algorithm>   
#include <functional>   
using namespace std;   

2. 建堆：
vector<int> a(n);    
   for(i=0;i<n;i++)
{
   int y;
   cin>>y;
   a[i]=y;
}
make_heap(a.begin

1. 时间复杂度为O（n^3）

2. 由于本题边数较多（n<500,e<2000），所以属稠密图，使用邻接矩阵记录

3. 建图时需剔除重边以及自环。

4. 通过Floyd算法，得到每两点间的最短路径

这个是上周整理的另一个最小生成树算法，通过Prim+Heap实现。

说明：
    1. heap使用的是stl中函数，我之后会将4种函数都贴出来

    2. 输入：第一行输入点数n、边数m，随后输入m条边的两端点与边长，再输入生成树的源点（防止图有不同的情况）

    3. 输出为最小生成树的总长，若要实现其他功能，可以以此为模板，添加代码

#include <iostream>
#include <vector>
#include <algorithm>