并查集模板
主要用于解决关于连通的一些问题
void Initial(){
for(int i=0;i<MAXN;i++){
father[i]=i;//根结点指向自己
height[i]=0;
//inDegree[i]=0;
//visit[i]=false;
}
}
int Find(int x){
if(father[x]!=x) father[x]=Find(father[x]);//注意写法，路径压缩
return father[x];
}
void Union(int x,int y){
x=Find(x);
y=Find(y);
if(x!=y){
if(height[x]<height[y]) father[x]=y;
else if(height[x]>height[y]) father[y]=x;//前面两种情况树高并没有变
else{
father[y]=x;
height[x]++;
}
}
return ;
}邻接表
struct Edge{
int to;
int length;
Edge(int t,int l):to{t},length(l){}
};
vector<Edge> graph[MAXN];广度优先搜索
struct Status{
int n,t;//t表示起点到n的时间
Status(int n,int t):n(n),t(t){}
};
bool visit[MAXN];
int BFS(int n,int k){
queue<Status> myqueue;
myqueue.push(Status(n,0)); //初始状态
visit[n]=true; //起始点已被访问
while(!myqueue.empty()){
Status current=myqueue.front();
myqueue.pop();
if(current.n==k) return current.t; //查找成功
for(int i=0;i<3;i++){ //转入三种不同的状态
Status next(current.n,current.t+1);
if(i==0) next.n+=1;
else if(i==1) next.n-=1;
else next.n*=2;
if(next.n<0||next.n>=MAXN||visit[next.n]) continue;//新状态不合法
myqueue.push(next);
visit[next.n]=true;//置访问标记
}
}
}深度优先搜索
int side; //边长
int m; //树枝数目
int sticks[MAXN];
bool visit[MAXN];
bool DFS(int sum,int number,int position){
if(number==3) return true;
int sample=0; //剪枝(3)
for(int i=position;i<m;i++){
if(visit[i]||sum+sticks[i]>side||sticks[i]==sample) continue;
visit[i]=true;
if(sum+sticks[i]==side){ //能凑成一条边
if(DFS(0,number+1,0)) return true;
else sample=sticks[i]; //记录失败的棍子的长度
}
else{
if(DFS(sum+sticks[i],number,i+1)) return true;
else sample=sticks[i]; //记录失败的棍子的长度
}
visit[i]=false;
}
return false;
}最小生成树
int Kruskal(int n,int edgeNumber){
Initial(n);
sort(edge,edge+edgeNumber);
int sum=0;
for(int i=0;i<edgeNumber;i++){
Edge current=edge[i];
//cout<<current.from<<"->"<<current.to<<" "<<current.length<<endl;
if(Find(current.from)!=Find(current.to)){
Union(current.from,current.to);
sum+=current.length;
}
}
return sum;
}最短路径
struct Point{//结点
int number;
int distance;
Point(int n,int d):number(n),distance(d){}
bool operator< (const Point& p) const{//重载小于
return distance>p.distance;
}
};
int dis[MAXN];
void Dijkstra(int s){
priority_queue<Point> pqueue;
dis[s]=0;
pqueue.push(Point(s,dis[s]));
while(!pqueue.empty()){
int u=pqueue.top().number;//离源点最近的点
pqueue.pop();
for(int i=0;i<graph[u].size();i++){
int v=graph[u][i].to;//u为顶点的编号，i为边的序号
int d=graph[u][i].length;
if(dis[v]>dis[u]+d){
dis[v]=dis[u]+d;
pqueue.push(Point(v,dis[v]));
}
}
}
return ;
}拓扑排序
int inDegree[MAXN];
vector<int> TopologicalSort(int n){
vector<int> topology;
priority_queue<int,vector<int>,greater<int> > node;//逆向优先队列，为了实现拓扑序列不唯一时编号小的在前面
for(int i=1;i<=n;i++){//i是从1到n，即结点的编号
if(inDegree[i]==0){//先把初始入度为零的全部放入队列
node.push(i);
}
}
//求解拓扑序列时一定先把上一层的所有全部入队后再入队下一层，所以优先队列不会干扰
while(!node.empty()){
int u=node.top();
node.pop();
topology.push_back(u);
for(int i=0;i<graph[u].size();i++){//遍历当前pop出的结点的所有出弧
int v=graph[u][i];
inDegree[v]--;
if(inDegree[v]==0){//u的所有出弧全部去掉后如果有入度为零的则push进队列
node.push(v);
}
}
}
return topology;
}关键路径
基于拓扑顺序去遍历的
void CriticalPath(int n){
vector<int> topology;//拓扑序列
queue<int> node;
for(int i=0;i<n;i++){
if(inDegree[i]==0){
node.push(i);
earliest[i]=1;//初始化为1,题目中的要求：1ns
}
}
while(!node.empty()){
int u=node.front();
topology.push_back(u);
node.pop();
for(int i=0;i<graph[u].size();i++){
int v=graph[u][i].to;
int l=graph[u][i].length;
earliest[v]=max(earliest[v],earliest[u]+l);//正向找最大，形成earliest
inDegree[v]--;
if(inDegree[v]==0) node.push(v);
}
}
for(int i=topology.size()-1;i>=0;i--){
int u=topology[i];
if(graph[u].size()==0) latest[u]=earliest[u];//汇点的最晚开始时间初始化
else latest[u]=INF;//非汇点的最晚开始时间的初始化
for(int j=0;j<graph[u].size();j++){
int v=graph[u][j].to;
int l=graph[u][j].length;
latest[u]=min(latest[u],latest[v]-l);//逆向找最小，形成latest
}
}
}