锐客网

  1. 首页 > it技术 > >

[SinGuLaRiTy]|[SinGuLaRiTy] 复习模板-图论

【SinGuLaRiTy-1041】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
计算树的直径

//方法：任选一个点作为起点进行一次BFS，找到最远点u。再以u为起点做一次BFS，找最长路即直径。 queuepoint; void bfs(int a,int dis[]) { memset(dis,inf,sizeof dis); dis[a]=0; point.push(a); int v ,u ; while(!point.empty()) { u=point.front(); point.pop(); for(node *p=adj[u]; p!=NULL; p=p->next) if(dis[(v=p->v)]>dis[u]+p->w) { dis[v]=dis[u]+p->w; point.push(v); } } }void solve()//输出直径长度 { bfs(1,dis); int flag=1; for(int i=2; i<=n; ++i) if(dis[flag]
LCA-返回a,b两点间的最短边权
返回a，b两点之间的最短边权 void dfs(int u) { int v ; for(node *p=adj[u]; p!=NULL; p=p->next) { v=p->v; f[v][0]=u ; dep[v]=dep[u]+1 ; dfs(v); } }void init() { dep[root]=0 ; dfs(root); f[root][0]=root ; for(int j=1; j=0; --j) if(dep[f[u][j]]>=val) u=f[u][j]; }int solve(int u,int v) { if(dep[u]>dep[v])adjust(u,dep[v]); else if(dep[u]=0; --j) if(f[u][j]!=f[v][j]) u=f[u][j] ,v=f[v][j]; return f[u][0]; }

LCA 最近公共祖先-在线倍增
#include #include #include #include #include #include using namespace std; const int N=100001,L=20; int m,first[N],next[N],d[N],f[N][L]; inline void dfs(int x,int dep) { d[x]=dep; m=max(m,dep); for (int i=first[x]; i; i=next[i]) dfs(i,dep+1); } int log2(int x) { int k=0; while (x>1) { x>>=1; k++; } return k; } int main() { int i,j,n,s,x,y,root; scanf("%d",&n); for (i=1; i<=n; i++) { scanf("%d",&f[i][0]); if (!f[i][0]) root=i; next[i]=first[f[i][0]]; first[f[i][0]]=i; } dfs(root,0); s=log2(m); for (j=1; j<=s; j++) for (i=1; i<=n; i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d",&n); while (n--) { scanf("%d%d",&x,&y); if (d[x]d[y]) { if (d[x]-(1<=d[y]) x=f[x][s]; s--; } s=log2(d[x]); while (s>-1) { if (f[x][s]!=f[y][s]) { x=f[x][s]; y=f[y][s]; } s--; } printf("%d\n",x==y?x:f[x][0]); } return 0; }

LCA 最近公共祖先-树链(双链树存图)
#include #include #include #include #include #include #define N 100001 using namespace std; int a[N*2],d[N],down[N],next[N],top,f[2*N][18],loc[2*N][18],n,b[N]; int log2(int x) { int k=0; while (x>1) { x/=2; k++; } return k; } void dfs(int x,int dep) { int i; d[x]=dep; a[++top]=x; for (i=down[x]; i!=0; i=next[i]) { dfs(i,dep+1); a[++top]=x; } } void init() { int i,j,s,x,k; for (i=1; i<=top; i++) { f[i][0]=d[a[i]]; loc[i][0]=a[i]; } s=log2(top); for (j=1; j<=s; j++) { k=top-(1<0) { t--; scanf("%d%d",&x,&y); x=b[x]; y=b[y]; if (x>y) swap(x,y); i=log2(y-x); k=y-(1<
LCA 最近公共祖先-tarjan算法
void tarjan(int u) { for(node *p=adj[u]; p!=NULL; p=p->next) { tarjan(p->v); Union(p->v,u); } vis[u]=1; for(int i=1; i<=ask[u][0]; ++i) if(vis[ask[u][i]]==1) printf("%d\n",getroot(ask[u][i])); }void init() { scanf("%d",&m); while(m--) { scanf("%d%d",&a,&b); ask[a][++ask[a][0]]=b; ask[b][++ask[b][0]]=a; } for(int i=1; i<=n; ++i) if(!in[i]) { tarjan(i); break; } }

前向星存图
struct node { int v ,w ; node *next ; }edge[MAXM<<1] ,*adj[MAXN] ,*code=edge ; void add(int a,int b,int c) { ++code; code->v=b ,code->w=c ,code->next=adj[a] ; adj[a]=code ; }

最短路-Dijkstra
#define inf 0x3f3f3f3f int dis[MAXN+5] ; bool flag[MAXN+5] ; void dijkstra(int a) { memset(dis,inf,sizeof dis); dis[a]=0; int minv ; for(int i=1; i<=n; ++i) { minv=0 ; for(int i=1; i<=n; ++i) if(!flag[i]&&dis[minv]>dis[i]) minv=i; if(minv==0)break; flag[minv]=1; for(node *p=adj[minv]; p!=NULL; p=p->next) dis[p->v]=min(dis[p->v],dis[minv]+p->w); } }

最短路-优先队列(堆优化的Dijkstra)
struct node { int v ,w ; node *next ; bool operator < (const node &a) const { return w>a.w; } }edge[MAXM<<1] ,*adj[MAXN] ,*code=edge ; priority_queue > q; //注意必须开结构体，因为若在队列中一个元素的dis发生改变，队列不会对它重新排序 void dijkstra(int a) { memset(vis,0,sizeof vis); memset(dis,inf,sizeof dis); dis[a]=0 ; q.push((node){a,0}); int u ,d ,v ; while(!q.empty()) { u=q.top().v ,d=q.top().w ; q.pop(); if(vis[u])continue; vis[u]=1; for(node *p=adj[u]; p!=NULL; p=p->next) if(!vis[(v=p->v)]&&dis[v]>dis[u]+p->w) { dis[v]=dis[u]+p->w; q.push((node){v,dis[v]}); } } }

最短路-SPFA+判断负权环路
#define inf 0x3f3f3f3f queuepoint; int dis[MAXN+5] ,vis[MAXN+5] ; bool in[MAXN+5] ; void spfa(int a) { int u ,v ; memset(dis,inf,sizeof dis); point.push(a); dis[a]=0 ,in[a]=vis[a]=1 ; while(!point.empty()) { u=point.front(); in[u]=0 ; point.pop(); for(node *p=adj[u]; p!=NULL; p=p->next) if(dis[(v=p->v)]>dis[u]+p->w) { dis[v]=dis[u]+p->w; if(!in[v]) { in[v]=1; point.push(v); if(++vis[v]>n) { puts("No Solution"); return; } } } } }

最短路-Floyd
int dis[MAXN+5][MAXN+5] ; void floyd() { for(int k=1; k<=n; ++k) for(int i=1; i<=n; ++i) if(k!=i) for(int j=1; j<=n; ++j) if(i!=j&&k!=j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); }

一笔画问题-欧拉回路
#include #include #define MAXN 105 using namespace std; int n ,m ,a ,b ,map[MAXN+5][MAXN+5] ,temp[MAXN<<1] ,du[MAXN] ,cnt ; int flag[5] ,pos ; void dfs(int u) { for(int v=1; v<=n; ++v) if(map[u][v]) { map[u][v]=map[v][u]=0; dfs(v); } temp[++cnt]=u ; } int main() { scanf("%d",&n); for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { scanf("%d",&map[i][j]); if(map[i][j])++du[i]; } for(int i=1; i<=n; ++i) if(du[i]&1) flag[++pos]=i ; if(pos!=0&&pos!=2) { puts("No Solution!"); return 0; } if(pos==0)flag[1]=flag[2]=1; dfs(flag[1]); for(int i=cnt; i>1; --i) printf("%d ",temp[i]); printf("%d\n",temp[1]); return 0; }

多叉树(森林)转二叉树
//输入N,M表示节点数和边数，再输入M组边关系，从1到N输出每个结点的父亲，根节点父亲为0 #include #include using namespace std; void read(int &x) { int f=1; x=0; char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1; s=getchar(); } while(s>='0'&&s<='9'){x=x*10+s-'0'; s=getchar(); } x*=f; } #define MAXN 100 struct node { int l,r,f; }tree[MAXN+5]; int N,M; int root[MAXN+5],rs; bool d[MAXN+5][MAXN+5]; void rtb()//处理森林 { for(int i=1; i<=N; i++) if(!tree[i].f) root[++rs]=i; for(int i=rs; i>1; i--) { tree[root[i-1]].r=root[i]; tree[root[i]].f=root[i-1]; } } int main() { read(N),read(M); for(int i=1; i<=M; i++) { int x,y; read(x),read(y); d[x][y]=1; //先保存起来 } for(int i=1; i<=N; i++)//再处理 for(int j=1; j<=N; j++) if(d[i][j]) { if(tree[i].l==0) { tree[i].l=j; tree[j].f=i; } else { int t=tree[i].l; while(tree[t].r) t=tree[t].r; tree[t].r=j; tree[j].f=t; } } rtb(); for(int i=1; i<=N; i++) { if(i
树的先序,中序,后序遍历-非递归版
//先序遍历 void PreOrder(Node* root) { assert(NULL != root) stack store; store.push(root); // 根结点入栈 while(!store.empty()) { root = store.top(); // 在循环中，root记录的是当前准备输出的结点 store.pop(); cout << root->value << ""; // 输出当前结点 if(root->right_child) // 右孩子入栈 store.push(root->right_child); if(root->left_child) // 左孩子入栈 store.push(root->left_child); } }//中序遍历 void InOrder(Node* root) { assert(NULL != root); stack store; while(root && !store.empty()) { if(root != NULL) { // 只要不为空，就一路向左结点方向走去 store.push(root); root = root->left_child; } else { // store.top()的左边都走过了 cout << store.top()->value << ""; // 输出当前结点 root = store.top()->right_child; store.pop(); } } }//后序遍历 void PostOrder(Node* root) { assert(NULL != root); Node* Pre = NULL; stack store; while(root && !store.empty()) { if(root != NULL) { // 一路向左 store.push(root); root = root->left_child; } else { // stack.top()的左子树都输出完了 if(store.top()->right_child!=NULL && store.top()->right_child!=Pre) { // 右子树存在且没有输出过 root = root->right_child; } else { // 左右子树都输出过了 cout << store.top()->value << ""; Pre = store.top(); store.pop(); } } } }

树的先序,中序,后序遍历-递归版
//先序遍历 void preOrder1(BinTree *root) { if(root!=NULL) { cout<data<<" "; preOrder1(root->lchild); preOrder1(root->rchild); } }//中序遍历 void inOrder1(BinTree *root) { if(root!=NULL) { inOrder1(root->lchild); cout<data<<" "; inOrder1(root->rchild); } }//后序遍历 void postOrder1(BinTree *root) { if(root!=NULL) { postOrder1(root->lchild); postOrder1(root->rchild); cout<data<<" "; } }

求树的重心
//以 POJ 1655 为例 //题意:给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的. #include #include #includeusing namespace std; const int N = 20005; const int INF = 1<<30; int head[N]; int son[N]; bool vis[N]; int cnt,n; int ans,size; struct Edge { int to; int next; }; Edge edge[2*N]; void Init() { cnt = 0; size = INF; memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); }void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; }void dfs(int cur) { vis[cur] = 1; son[cur] = 0; int tmp = 0; for(int i=head[cur]; ~i; i=edge[i].next) { int u = edge[i].to; if(!vis[u]) { dfs(u); son[cur] += son[u] + 1; tmp = max(tmp,son[u] + 1); } } tmp = max(tmp,n-son[cur]-1); if(tmp < size || tmp == size && cur < ans) { ans = cur; size = tmp; } }int main() { int T; scanf("%d",&T); while(T--) { Init(); scanf("%d",&n); for(int i=1; i<=n-1; i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1); printf("%d %d\n",ans,size); } return 0; }

最小生成树-Kruskal
#include #include #include #include using namespace std; const int MAXN = 1010, MAXM = 100010; int N, M; struct Edge { int a, b, d; bool operator < (const Edge&t) const { return d < t.d; } } ed[MAXM]; int tfa[MAXN]; void init() { for (int i = 1; i<=N; ++i) tfa[i] = i; } int root(int x) { if (x == tfa[x]) return x; return tfa[x] = root(tfa[x]); } void unite(int x, int y) { tfa[root(x)] = root(y); }int Kruskal() { sort(ed+1, ed+M+1); int i, cnt = 0, a, b, ans = 0; for (i = 1; i<=M && cnt
最小生成树-Prim
#include #include #include #include using namespace std; const int MAXN = 5010, MAXM = 500010; const int INF = 0x3f3f3f3f; int N, M; struct Node { int to, d; Node *next; }Edge[MAXM*2], *ecnt=Edge, *adj[MAXN]; void addedge(int a, int b, int c) { (++ecnt)->to = b; ecnt->d = c; ecnt->next = adj[a]; adj[a] = ecnt; }bool vis[MAXN]; struct Near { int to, d; Near(){} Near(int a,int b){to=a; d=b; } bool operator < (const Near&t) const { return d > t.d; } }; int prim() { int cnt = 0, ans = 0; priority_queue Q; Q.push(Near(1, 0)); while (cnt < N && !Q.empty()) { int u = Q.top().to, d = Q.top().d; Q.pop(); if (vis[u]) continue; ans += d; vis[u] = 1; ++cnt; for (Node*p = adj[u]; p; p=p->next) if (!vis[p->to]) Q.push(Near(p->to, p->d)); } return ans; }int main() {return 0; }

拓扑排序-Toposort
int ans[MAXN+5] ; bool vis[MAXN+5] ; void topo() { int flag ; for(int i=1; i<=n; ++i) { flag=0; for(int j=1; j<=n; ++j) if(!vis[j]&&!in[j]) {flag=j; break; } if(!flag) { puts("no solution"); return; } ans[i]=flag ,vis[flag]=1 ; for(node *p=adj[flag]; p!=NULL; p=p->next) --in[p->v]; } for(int i=1; i
求割点
int low[MAXN] ,dfn[MAXN] ,cnt ,root_son ; bool cutp[MAXN] ; void dfs(int u,int fa) { int v ; low[u]=dfn[u]=++cnt ; for(node *p=adj[u]; p!=NULL; p=p->next) { v=p->v; if(!dfn[v]) { dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u])//在这里注意打上{}{ if(fa!=-1)cutp[u]=1 ; else ++root_son; } } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } void tarjon() { memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cnt=0; for(int i=1; i<=n; ++i) if(!dfn[i]) { root_son=0 ; dfs(i,-1); cutp[i]=root_son-1 ; } }

求割边(即桥)
int low[MAXN] ,dfn[MAXN] ,cnt ,root_son ; int cnte[MAXM][2] ,pos ; void dfs(int u,int fa) { int v ; low[u]=dfn[u]=++cnt ; for(node *p=adj[u]; p!=NULL; p=p->next) { v=p->v; if(!dfn[v]) { dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) cnte[++pos][0]=u ,cnte[pos][1]=v ; } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } void tarjon() { memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cnt=0; for(int i=1; i<=n; ++i) if(!dfn[i]) dfs(i,-1); }

双联通分量
stack< pair >e; pairtmp ; int dfn[MAXN] ,low[MAXN] ,cnt ,pos ; void dfs(int u,int fa) { low[u]=dfn[u]=++cnt ; int v ; for(node *p=adj[u]; p!=NULL; p=p->next) { v=p->v; if(!dfn[v]) { e.push(make_pair(u,v)); dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { printf("Block No. %d\n",++pos); do { tmp=e.top(); e.pop(); printf("%d, %d\n",tmp.first,tmp.second); }while(tmp.first!=u||tmp.second!=v); } } else if(v!=fa) { low[u]=min(low[u],dfn[v]); if(dfn[u]>low[v]) e.push(make_pair(u,v)); } } } void tarjon() { memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cnt=0; for(int i=1; i<=n; ++i) if(!dfn[i]) dfs(i,-1); }

有向图强连通分量
int cnt ,pos ,low[MAXN+5] ,dfn[MAXN+5] ,block[MAXN+5] ; void dfs(int u) { int v ; low[u]=dfn[u]=++cnt; in[u]=1 ; stack[++tail]=u; for(node *p=adj[u]; p!=NULL; p=p->next) { v=p->v; if(!dfn[v]) { dfs(v); low[u]=min(low[u],low[v]); } else if(in[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++pos; do { block[stack[tail]]=pos; in[stack[tail]]=0; //忘记删除标记- - --tail; }while(stack[tail+1]!=u); } } void tarjon() { memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cnt=pos=0; for(int i=1; i<=n; ++i) if(!dfn[i]) dfs(i); }

二分图判定-DFS
//以 HDU 2444 为例 //题意：给出一个无向图，若为二分图则求最大匹配，否则输出"No"。 #include #include #includeusing namespace std; const int N = 2005; int head[N],link[N]; bool vis[N],col[N]; int cnt,n,m; struct Edge { int to; int next; }; Edge edge[N*N]; void Init() { cnt = 0; memset(head,-1,sizeof(head)); memset(col,0,sizeof(col)); }void add(int u,int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; }bool Color(int u) { for(int i=head[u]; ~i; i=edge[i].next) { int v = edge[i].to; if(!col[v]) { col[v] = !col[u]; if(!Color(v)) return false; } else if(col[v] == col[u]) return false; } return true; }bool dfs(int u) { for(int i=head[u]; ~i; i=edge[i].next) { int v = edge[i].to; if(!vis[v]) { vis[v] = 1; if(link[v] == -1 || dfs(link[v])) { link[v] = u; return true; } } } return false; }int match() { int ans = 0; memset(link,-1,sizeof(link)); for(int i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } return ans; }int main() { while(~scanf("%d%d",&n,&m)) { if(n == 1) { puts("No"); continue; } Init(); while(m--) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } col[1] = 1; if(!Color(1)) { puts("No"); continue; } printf("%d\n",match()>>1); } return 0; }

二分图最大匹配-匈牙利算法
bool dfs(int u) { for(int v=1; v<=cntx; ++v) if(!vis[v]&&map[u][v]) { vis[v]=1; if(!cy[v]||dis(cy[v])) { cx[u]=v ,cy[v]=u ; return 1; } } return 0; } int match() { memset(cx,0,sizeof cx); memset(cy,0,sizeof cy); int ans=0; for(int i=1; i<=cntx; ++i) if(!cx[i]) { memset(vis,0,sizeof vis); ans+=dfs(i); } return ans; }

二分图最佳匹配-KM算法
const int inf=1e9,maxn=510; int KM(int m,int n,int tu[][maxn],int *match1,int *match2) { int s[maxn],t[maxn],l1[maxn],l2[maxn],p,q,ret=0,i,j,k; ///l1为左边的匹配分量，l2是右边的匹配分量 for(i=0; il1[i]?tu[i][j]:l1[i]; if(l1[i]==-inf) return -1; } for(i=0; i=0; j=p) match2[j]=k=t[j],p=match1[k],match1[k]=j; } } if(match1[i]<0) { for(i--,p=inf,k=0; k<=q; k++) for(j=0; j 网络流-SAP
//以HDU 3549为例 #include #include #include using namespace std; typedefstruct {int v,next,val; } edge; const int MAXN=20010; const int MAXM=500010; edge e[MAXM]; int p[MAXN],eid; inline void init(){memset(p,-1,sizeof(p)); eid=0; } //有向 inline void insert1(int from,int to,int val) { e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; swap(from,to); e[eid].v=to; e[eid].val=0; e[eid].next=p[from]; p[from]=eid++; } //无向 inline void insert2(int from,int to,int val) { e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; swap(from,to); e[eid].v=to; e[eid].val=val; e[eid].next=p[from]; p[from]=eid++; } int n,m; //n为点数 m为边数 int h[MAXN]; int gap[MAXN]; int source,sink; inline int dfs(int pos,int cost) { if (pos==sink) { return cost; } int j,minh=n-1,lv=cost,d; for (j=p[pos]; j!=-1; j=e[j].next) { int v=e[j].v,val=e[j].val; if(val>0) { if (h[v]+1==h[pos]) { if (lv=n) return cost-lv; if (lv==0) break; } if (h[v]
最大流-ISAP
#include #include #include using namespace std; #define Min(a,b) ((a)<(b)?(a):(b)) #define clear(a) memset(a,0,sizeof a) const int MAXN = 1010, MAXM = 10010; const int INF = 1<<29; struct Node { int to, c; Node*next, *back; }; struct FlowNet { int S, T, vn; int d[MAXN], vd[MAXN]; Node Edge[MAXM], *ecnt, *adj[MAXN]; FlowNet() { ecnt=Edge; } void init(int a, int b, int c) { S = a; T = b; vn = c; } void addedge(int a, int b, int c) { (++ecnt)->to = b; ecnt->c = c; ecnt->next = adj[a]; adj[a] = ecnt; ecnt->back = ecnt+1; (++ecnt)->to = a; ecnt->c = 0; ecnt->next = adj[b]; adj[b] = ecnt; ecnt->back = ecnt-1; } int aug(int u, int augco) { if (u == T) return augco; int augc = augco, mind = vn-1, delta; for (Node*p = adj[u]; p; p=p->next) if (p->c > 0) { if (d[u] == d[p->to]+1) { delta = aug(p->to, Min(p->c, augc)); augc -= delta; p->c -= delta; p->back->c += delta; if (d[S]>=vn) return augco-augc; if (!augc) break; } mind = Min(mind, d[p->to]); } if (augc == augco) { if (!--vd[d[u]]) d[S] = vn; ++vd[d[u] = mind+1]; } return augco - augc; } int ISAP() { int flow = 0; clear(d); clear(vd); vd[0] = vn; while (d[S] < vn) flow+=aug(1, INF); return flow; } } G; int N, M; int main() { int a, b, c; scanf("%d%d", &M, &N); G.init(1, N, N); for (int i = 1; i<=M; ++i) { scanf("%d%d%d", &a, &b, &c); G.addedge(a, b, c); } printf("%d\n", G.ISAP()); return 0; }

第K短路-K-th_Short
#include #include #include using namespace std; #define MAXM 100005 #define MAXN 1005 const int INF = 1<<28; int N, M, S, T, K; struct Node { int to, len; Node *next; }Edge[MAXM*4], *ecnt = Edge, *adj[MAXN], *radj[MAXN]; void addedge(int a, int b, int c) { ++ecnt; ecnt->to = b; ecnt->len = c; ecnt->next = adj[a]; adj[a] = ecnt; ++ecnt; ecnt->to = a; ecnt->len = c; ecnt->next = radj[b]; radj[b] = ecnt; } struct dijs { int u, dis; dijs () {} dijs (int a,int b) {u=a; dis=b; } bool operator < (const dijs&a) const { return dis > a.dis; } }; int rdis[MAXN]; bool vis[MAXN]; priority_queue dij; void rDijkstra() //边反向跑最短路以获取H函数值 { memset(rdis, 0x3f, sizeof rdis); rdis[T] = 0; dij.push(dijs(T, 0)); dijs t; while (!dij.empty()) { t = dij.top(); dij.pop(); if (vis[t.u]) continue; vis[t.u] = 1; for (Node *p = radj[t.u]; p; p=p->next) if (rdis[p->to] > t.dis + p->len) { rdis[p->to] = t.dis + p->len; dij.push(dijs(p->to, rdis[p->to])); } } } struct ss { int u, pre; ss () {} ss (int a, int b) { u=a; pre=b; } bool operator < (const ss&a) const { return pre+rdis[u] > a.pre+rdis[a.u]; //pre是G函数值，rdis是H函数值，根据两个之和判定优先级。} }; int Tvisn; //第几次到达T点 priority_queue as; int Astar() { if (S==T) Tvisn = -1; //如果起点终点相等，一开始不算到达终点 as.push(ss(S, 0)); ss t; while (!as.empty()) { t = as.top(); as.pop(); if (t.u == T) { ++Tvisn; if (Tvisn == K) return t.pre; //根据A*算法的正确性，第K次到达即为第K短路} for (Node *p = adj[t.u]; p; p=p->next) as.push(ss(p->to, t.pre + p->len)); } return -1; } int main() { int i, a, b, c; scanf("%d%d", &N, &M); for (i = 1; i<=M; ++i) { scanf("%d%d%d", &a, &b, &c); addedge(a, b, c); } scanf("%d%d%d", &S, &T, &K); rDijkstra(); printf("%d\n", Astar()); return 0; }


Time: 2017-10-16
【[SinGuLaRiTy]|[SinGuLaRiTy] 复习模板-图论】转载于:https://www.cnblogs.com/SinGuLaRiTy2001/p/7674849.html

    推荐阅读


    上一篇：HTML|HTML 转义符

    下一篇：【转载】CSS|【转载】CSS Selector参考手册