图论

技巧：要判断一遍dfs能否走完所有节点，可以判断这些节点的父亲是否相同，如果相同则可以走完所有节点，否则不能。

链式前向星存图 

struct edge{
    int val,v,next;
}edge[2005];
int head[2005],cnt;
void init()
{
    for(int i = 0; i <= n; i++) head[i] = -1;
}

void add(int u,int v,int val)
{
    edge[cnt].v = v;
    edge[cnt].val = val;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int main()
{ 
    init();
    return 0;
}

打印路径 

void path(int x,int s,int d)
{
    if(s == d) {
        printf("%d",s);
        return;
    }
    path(s,pre[d]);//先输出前一个
    printf(" %d",d);//再输出后一个
}

SPFA+链式前向星模板

O(n*m)支持负权
SPFA 队列+链式前向星模板 

struct S{
   int next,e,v;
}edge[105];
int head[105];
int d[105];
bool inq[105];
int n,m,a,b,c,cnt;

void add(int a,int b,int c)
{
    edge[++cnt].next = head[a];
    edge[cnt].e = b;
    edge[cnt].v = c;
    head[a] = cnt;
}

void spfa(int t)
{
    for(int i = 0; i <= n; i++){
        d[i] = 1000000;
        inq[i] = false;
    }
    queue<int>q;
    q.push(1);
    d[1] = 0;
    inq[1] = true;
    while(!q.empty()){
        int s = q.front();
        q.pop();
        inq[s] = false;
        for(int i = head[s];i != 0; i = edge[i].next){
            int u = edge[i].e,w = edge[i].v;
            if(d[u] > d[s] + w){
               d[u] = d[s] + w;
               if(!inq[u]){
                inq[u] = true;
                q.push(u);
               }
            }
        }
    }
   printf("%d\n",d[n]);
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        if(n == 0 && m == 0) break;
        cnt = 0;
        for(int i = 1; i <= n; i++) edge[i].next = 0,head[i] = 0;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        spfa(1);
    }
    return 0;
}

最小生成树

kruskal算法：对每条变按边权值从小到大排列，然后优先选取边权值小的边，判断两点的父亲是否相同，如果相同不选，不相同加入，利用并查集判断。
https://nanti.jisuanke.com/t/43111
这道题只要选出n-k个人即可，所有人直接或间接认识说明所有人可以用一根线连起来（也可以说父亲相同）。 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct edge{
    int u,v,val;
    bool operator < (const edge &a) const{
        return val < a.val;
    }
}edge[400005];

int f[200005];
int find(int x)
{
    if(x != f[x]) f[x] = find(f[x]);
    return f[x];
}

int main()
{
    ios::sync_with_stdio(false);
    int m,n,k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= m; i++) cin >> edge[i].u >> edge[i].v >> edge[i].val;
    sort(edge+1,edge+m+1);
    int cnt = 1;
    ll sum = 0;
    for(int i = 1; i <= m; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        u = find(edge[i].u);
        v = find(edge[i].v);
        if(u == v) continue;
        f[u] = v;
        sum += 1ll*edge[i].val;
        if(cnt++ == n - k) break;
    }
    cout << sum << endl;
    return 0;
}

K短路

相关问题

1：判断一条边是否在1-n的最短路上

先求源点为1的单源最短路dist1，再求以n为源点的单源最短路dist2，然后再枚举每条边（u，v），如果dist1[u]+len[u,v]+dist2[v]=min或者是dist1[v]+len[u,v]+dist2[u]=min,则说明这条边在最短路上，否则不在。
https://ac.nowcoder.com/acm/contest/5158/E 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct Edge{
    int u,v,w;
    Edge(int f,int to,int val){
        u = f,v = to,w = val;
    }
};

struct node{
    int opt;
    ll va;
    node(int a,ll b){
        opt = a;
        va  = b;
    }
    bool operator < (const node &a) const{
        return va > a.va;
    }
        //或者下面这样写
        //friend    bool operator < (node a,node b){
        //    return a.va > b.va;
       //}
};
ll vis[1000005],dvis[100005],h[1000005],cnt,n,m,k,t;
ll l[1000005],l1[2000005],l2[1000005];
int U[1000005],V[1000005],W[1000005];
vector<Edge>edge[1000005];
void dijkstra(int d)
{
    for(int i = 1; i <= n; i++) l[i] = mod*(double)100000,vis[i] = 0;
    priority_queue<node>q;
    l[d] = 0;
    q.push(node(d,0));
    while(!q.empty()){
      node s = q.top();//node s只能写在这。
        int u = s.opt;
        ll W = s.va;
        //cout << u << " ";
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = 0; i < edge[u].size(); i++){
            Edge y = edge[u][i];
            //cout << i << endl;
            if(vis[y.v]) continue;
            if(l[y.v] > W + y.w){
                l[y.v] = W + y.w;
                q.push(node(y.v,l[y.v]));
            }
        }
    }
}

int find(int x)
{
    if(x == h[x]) return x;
    return h[x] = find(h[x]);
}

void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x != y) h[y] = x;
}

int main()
{
    ios::sync_with_stdio(false);
            cin >> n >> m;
            int a,b,c;
            for(int i = 0; i <= n; i++) h[i] = i;
            for(int i = 1; i <= m; i++){
                cin >> U[i] >> V[i] >> W[i];
                edge[U[i]].push_back(Edge(U[i],V[i],W[i]));
                edge[V[i]].push_back(Edge(V[i],U[i],W[i]));
            }
            dijkstra(1);
            for(int i = 1; i <= n; i++) l1[i] = l[i];
            dijkstra(n);
            for(int i = 1; i <= n; i++) l2[i] = l[i];
            for(int i = 1; i <= m; i++){
                    if(l1[U[i]] + 1ll*W[i] + l2[V[i]] == l1[n] || l1[V[i]] + 1ll*W[i] + l2[U[i]] == l1[n]){
                        continue;
                    }
                    merge(U[i],V[i]);
                }
            int cnt = 0;
            for(int i = 1; i <= n; i++){
                if(h[i] == i) cnt++;
            }
            if(cnt == 1) cout << "YES\n";
            else cout << "NO\n"; 
    return 0;
}

2：n个起点，m个终点，求这n个起点中的任意一点到m个终点中任意一点的最短路

建一个超级源点s，从s的n个起点分别连一条权值为零的边，建立一个超级汇点，从m个终点到t分别连一条权值为零的边，然后求s-t的最短路即可。

3：求有向图中所有点到n点的最短路。

反向建图，以n为源点求单源最短路。
（起点和终点交换，方向相反，问题等效）
https://www.jisuanke.com/course 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct edge{
    int v,w,next;
}edge[2][60005];


struct node{
    int opt;
    ll w;
    node(int a,ll k){
        opt = a;
        w   = k;
    }
    bool operator < (const node &p) const{
        return w > p.w;
    }
};
int head[2][20005],v[20005],cnt,cnt1,m,n,t;
void add(int u,int v,int w)
{
    edge[0][cnt].next = head[0][u];
    edge[0][cnt].v = v;
    edge[0][cnt].w = w;
    head[0][u] = cnt++;
}

void add1(int u,int v,int w)
{
    edge[1][cnt1].next = head[1][u];
    edge[1][cnt1].v = v;
    edge[1][cnt1].w = w;
    head[1][u] = cnt1++;
}

void init()
{
    for(int i = 1; i <= n; i++) head[0][i] = -1,head[1][i] = -1;
}

void dijkstra(int l,int dy,ll d[])
{
    priority_queue<node>q;
    for(int i = 1; i <= n; i++) d[i] = ds,v[i] = 0;
    d[dy] = 0;
    q.push(node(dy,0));
    while(!q.empty()){
        node s = q.top();
        q.pop();
        int t = s.opt;
        ll w = s.w;
        if(v[t]) continue;
        v[t] = 1;
        for(int i = head[l][t]; ~i; i = edge[l][i].next){
            int va = edge[l][i].w;
            int k = edge[l][i].v;
            if(v[k]) continue;
            if(d[k] > w + 1ll*va){
                d[k] = w + 1ll*va;
                q.push(node(k,d[k]));
            }
        }
     }
}

int main()
{
    ios::sync_with_stdio(false);
    ll d[20005],d1[20005];
    cin >> t;
    while(t--){
        cin >> n >> m;
        int u,v,w;
        cnt = 0,cnt1 = 0;
        memset(d,0,sizeof(d));
        memset(d1,0,sizeof(d1));
        init();
        for(int i = 1; i <= m; i++){
            cin >> u >> v >> w;
            add(u,v,w);
            add1(v,u,w);
        }
        dijkstra(0,1,d);
        dijkstra(1,1,d1);
    //    for(int i = 1; i <= n; i++) cout << d[i] << endl;
    //    for(int i = 1; i <= n; i++) cout << d1[i] << endl;
        ll sum = 0;
        for(int i = 1; i <= n; i++){
            sum += d[i] + d1[i];
        }
        cout << sum << endl;
    }
    return 0;
}

树的重心

树的直径


定义：树中两点间距离的最大值称为直径
性质：

1、直径两端点一定是两个叶子节点

2、距离任意点最远的点一定是直径的一个端点，这个基于贪心求直径方法的正确性可以得出

3、对于两棵树，如果第一棵树直径两端点为(u,v)(u,v)，第二棵树直径两端点为(x,y)(x,y)，用一条边将两棵树连接，那么新树的直径一定是u,v,x,y,u,v,x,y,中的两个点

证明：如果新树直径不是原来两棵树中一棵的直径，那么新直径一定经过两棵树的连接边，新直径在原来每棵树中的部分一定是距离连接点最远的点，即一定是原树直径的一个端点。

4、对于一棵树，如果在一个点的上接一个叶子节点，那么最多会改变直径的一个端点

证明：假设在xx下面接一个点yy，直径变成了(u,x)(u,x),原树直径为(a,b)(a,b)，那么dis(u,x)>dis(a,b),dis(u,x)=dis(u,y)+1dis(u,x)>dis(a,b),dis(u,x)=dis(u,y)+1，即dis(u,y)+1>dis(a,b)dis(u,y)+1>dis(a,b)，如果dis(u,y)<dis(a,b)dis(u,y)<dis(a,b)，那么显然不成立；如果dis(u,y)=dis(a,b)dis(u,y)=dis(a,b)，那么(u,y)(u,y)也是原树的直径，符合上述结论。

5、若一棵树存在多条直径，那么这些直径交于一点且交点是这些直径的中点

求法：
一：两遍dfs/bfs
1）先任意对一个点做一次BFS，找到离这个点最远的一个点，作为直径的一个端点。
2）再对这个端点做一个BFS，找到里这个端点最远的一个点作为直径的另一端点，两端点间的距离就是树的直径。
二：dp
思路：先求出当前节点最远的儿子再求次远的儿子，二者求和。
状态 dp[x]: 表示以节点x为根的子树能够到达的最远的距离
状态转移：x节点的儿子为，y1,y2,y3,....，dp[x] = max{dp[y] + edge(x,y)}
代码： 
vector<int>a[100005];
int dp[100005],ans = 0;
void dfs(int so,int fa)
{
	int l = a[so].size();
	for(int i = 0; i < l; i++){
		int v = a[so][i];
		if(v == fa) continue;
		dfs(v,so);
		ans = max(ans,dp[so]+dp[v]+1);
		dp[so] = max(dp[so],dp[v]+1);
	}
}


pta-紧急救援:djikstra 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

struct edge{
	int v,next,w;
}edge[5005];

struct node{
	int x,w;
	node(int a,int b){
		x = a;
		w = b;
	}
	bool operator<(const node& a)const{
	    return w > a.w;
	}
};

int n,m,s,d;
int val[505];
int head[505],pre[505],num[505],dir[505],vis[505],num1[505],cnt = 0;

void add(int u,int v,int w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

void init()
{
	for(int i = 0; i <= n; i++) head[i] = -1;
}

void dij(int s)
{
	for(int i = 0; i <= n; i++) dir[i] = mod,vis[i] = 0;
	priority_queue<node>q;
	dir[s] = 0;
	q.push(node(s,0));
	num1[s] = val[s];
	num[s] = 1;
	while(!q.empty()){
		node t = q.top();
		q.pop();
		int k = t.x;
		if(vis[k]) continue;
		vis[k] = 1;
		for(int i = head[k]; ~i; i = edge[i].next){
			//cout << i << endl;
			int v = edge[i].v;
			int w = edge[i].w;
			if(vis[v]) continue;
			if(dir[v] > t.w + w){
				num[v] = num[k];
				dir[v] = t.w + w;
				num1[v] = num1[k] + val[v];
			    pre[v] = k;
				q.push(node(v,dir[v]));
			}
			else if(dir[v] == t.w + w){
				num[v] += num[k];
				if(num1[v] < num1[k] + val[v])
				    num1[v] = num1[k] + val[v],pre[v] = k;
			} 
		}
	}
}

void print(int s,int d)
{
	if(s == d){
		printf("%d",s);
		return;
	}
	print(s,pre[d]);
	printf(" %d",d);
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&d);
	for(int i = 0; i < n; i++){
		scanf("%d",&val[i]);
	}
	init();
	int v,u,w;
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dij(s);
	printf("%d %d\n",num[d],num1[d]);
	print(s,d);
	return 0;
}

欧涛的最短路

思路：连接每个点做成边，然后把边长小于等于m的边存入图中，最后dijkstar()求最短路。妙呀！！！ 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

struct edge{
	int v,next;
	double w;
}edge[5005];

struct node{
	int x;
	double len;
	node(int a,double w){
		x = a;
		len = w;
	}
	bool operator < (const node& a) const{
	    return len > a.len;
	}
};

struct D{
	double x,y,z;
}a[605];

int cnt = 0,head[605],vis[605],pre[605],b[605],n;
double m,d[605];
void add(int u,int v,double w)
{
	edge[cnt].v =  v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

void init()
{
	for(int i = 0; i <= n+2; i++) head[i] = -1;
}

void dijkstra()
{
	priority_queue<node>q;
	for(int i = 1; i <= n+2; i++) d[i] = 1000000000,vis[i] = 0;
	d[1] = 0;
	q.push(node(1,0));
	while(!q.empty()){
	//	cout << 1 << endl;
		node s = q.top();
		q.pop();
		if(vis[s.x]) continue;
		vis[s.x] = 1;
		for(int i = head[s.x]; ~i; i = edge[i].next){
			int v = edge[i].v;
			double w = edge[i].w;
			if(vis[v]) continue;
			if(d[v] > d[s.x] + w){
				d[v] = d[s.x] + w;
				pre[v] = s.x;
				q.push(node(v,d[v]));
			}
		}
	}
}
int cnt1 = 0;
void get_path(int s,int t)
{
	if(s == t){
		b[cnt1++] = s;
		return ;
	}
	get_path(s,pre[t]);
	b[cnt1++] = t;
}

int main()
{
	int x1,x2,y1,y2,z1,z2;
	cin >> n >> m;
	cin >> a[1].x >> a[1].y >> a[1].z >> a[n+2].x >> a[n+2].y >> a[n+2].z;
	init();
	for(int i = 2; i <= n+1; i++){
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	double x;
	for(int i = 1; i <= n+2; i++){
		for(int j = i+1; j <= n+2; j++){
			x = sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));
			if(x <= m){
				add(i,j,x);
				add(j,i,x);
			}
		}
	}
	dijkstra();
	if(d[n+2] == 1000000000){
		cout << "-1" << endl;
	}
	else{
		get_path(1,n+2);
		printf("%.3f\n",d[n+2]);
		cout << "Start ";
		for(int i = 1; i < cnt1-1; i++){
			cout << b[i] - 1 << " ";
		}
		cout << "End" << endl;
	}
	return 0;
}


{
    if(s == d) {
        printf("%d",s);
        return;
    }
    path(s,pre[d]);//先输出前一个
    printf(" %d",d);//再输出后一个
}
全部评论

相关推荐

昨天 17:17
已编辑
苏州大学 设计
作为面试官，比较喜欢听到「实习收获」回答是什么样的？
这是个老生常谈的问题，但凡有过实习/工作经验都会被问到。如何拥有近乎完美的回答？可以给一个思路模版。❗️提醒大家可以先在实习结束期速速复盘一下工作内容，趁着热乎劲，记忆会更加深刻。我比较注重连贯性，侧重个人的成长过程。以下是思路：第一段实习:初次接触这个行业，掌握了基本知识，尤其是锻炼自己的快速学习xx能力，通过xxx等方式快速补齐短板，也是在这段经历中发现了自己对xxx的兴趣第二段实习:继续拓宽自己的能力圈，学习到硬技能包括xxx，同时通过xxx工作培养了人际沟通和团队协调能力第三段实习:能够独立去负责一些项目，和过去的两段实习相比，在xxx方面成长了总结：通过这几段实习经历，积累了xxx感...
毕业季，给职场新人一些建议 面试问题记录
点赞 评论 收藏
分享
05-29 23:01
Université d’Auvergne-Clermont-Ferrand 1 C++
互联网c++开发岗位偏少，测开怎么样？
通过题目，不难看出问这个问题的，就是没工作过的。如果工作过，那就是不断往深的钻研，路越走越窄，找工作一般就是找原来方向的。没工作过的，那一般就是学生。&nbsp;学生，应届生找互联网工作（注意我单纯说的是找互联网工作）广撒网就完事了，找个厂子规模大知名的钱多的。尤其，现在这互联网哐哐裁员的情况，还进军互联网的，向钱看就行了。&nbsp;不要说，对某个方向比较喜欢，非它不可。找工作不是找对象，要相信爱情，忠贞不一。找工作是为了早日实现财富自由，就算你真的喜欢某个方向，如果让你每天9105，你还会喜欢吗。这年代爱情都不一定能经受住考验，更何况工作呢。&nbsp;所以，我认为现在干互联网---》就是为了挣快钱挣大钱；&nbsp;想找个挣钱...
点赞 评论 收藏
分享
04-21 13:58
江西财经大学 Java
点赞 评论 收藏
分享
05-27 16:58
西安电子科技大学 Java
点赞 评论 收藏
分享
05-29 18:22
江西农业大学 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的实习收获 #
9268次浏览 189人参与
# TP-LINK工作体验 #
46732次浏览 825人参与
# 实习吐槽大会 #
11697次浏览 52人参与
# 我的租房踩坑经历 #
1711次浏览 45人参与
# 晒一晒你的工位 #
77945次浏览 262人参与
# 你的办公桌上都有什么？ #
6310次浏览 52人参与
# 入职第三天，晒晒你的工位 #
30909次浏览 147人参与
# 实习中的菜狗时刻 #
359828次浏览 3274人参与
# 工作压力大怎么缓解 #
78127次浏览 929人参与
# 机械制造2023笔面经 #
115917次浏览 747人参与
# 今年形式下双非本找得到工作吗 #
137969次浏览 1042人参与
# Offer比较，求稳定还是求发展 #
52389次浏览 248人参与
# 电网笔面经互助 #
33259次浏览 331人参与
# 来选选带哪个offer回家过年 #
659670次浏览 5271人参与
# 机械专业只有考研才有出路吗 #
104343次浏览 866人参与
# 薪资一样，你会选择去大厂还是小公司 #
19291次浏览 116人参与
# 24届的你们现状如何了？ #
69557次浏览 399人参与
# 你觉得机械有必要实习吗 #
50794次浏览 445人参与
# 我的第一份实习怎么找的 #
102583次浏览 1020人参与
# 你的秋招第一场笔试是哪家 #
129418次浏览 1404人参与
牛客网
牛客企业服务