图论
技巧：要判断一遍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);//再输出后一个
}
查看9道真题和解析
投递大连飞创信息技术有限公司等公司6个岗位