单源最短路问题
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！
他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。
农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。
这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。
除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。
每条道路有一个通过费用（包括油费，过路费等等）。
给定一个地图，包含 C 条直接连接 2 个城镇的道路。
每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。
求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。
输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;
第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。
输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。
数据保证至少存在一条道路。
数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000
输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7
//SPFA算法
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 20000;
int head[N],to[N],nxt[N],w[N],idx=1;
int v[N],n,m,s,t,d[N];
queue<int> q;
void add(int a,int b,int c)
{
to[idx]=b;
w[idx]=c;
nxt[idx]=head[a];
head[a]=idx++;
}
int spfa()
{
memset(d,0x3f,sizeof(d));
d[s]=0;
v[s]=true;
q.push(s);
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=false;
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
if(!v[j])
{
q.push(j);
v[j]=true;
}
}
}
}
return d[t];
}
int main()
{
cin>>n>>m>>s>>t;
memset(head,-1,sizeof(head));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
cout<<spfa();
}
战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。
指挥部设在第一个哨所。
当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 n 个哨所全部接到命令后，送信才算成功。
因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。
现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。
输入格式
第 1 行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。
第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要花费 k 天。
输出格式
一个整数，表示完成整个送信过程的最短时间。
如果不是所有的哨所都能收到信，就输出-1。
数据范围
1≤n≤100,
1≤m≤200,
1≤k≤1000
输入样例：
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例：
11
//Floyd
#include<iostream>
#include <queue>
#include<cstring>
using namespace std;
const int N = 400;
int d[N][N];
int n,m,k;
int main()
{
cin>>n>>m;
memset(d,0x3f,sizeof(d));
d[1][1]=0; //一定要初始化距离
while (m -- )
{
int a,b,c;
cin>>a>>b>>c;
d[b][a]=d[a][b]=min(d[a][b],c);
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
bool flag=false;
int ans=0;
for(int i=1;i<=n;i++)
{
if(d[1][i]> 0x3f3f3f3f/2)
{
flag=true;
break;
}
ans=max(ans,d[1][i]);
}
if(flag)
{
cout<<-1<<endl;
}
else cout<<ans<<endl;
}
//spfa算法
#include<iostream>
#include <queue>
#include<cstring>
using namespace std;
const int N = 300;
int d[N],v[N];
queue<int> q;
int n,m;
int head[N],to[N],nxt[N],w[N],i=0;
void add(int a,int b,int c)
{
to[i]=b;
w[i]=c;
nxt[i]=head[a];
head[a]=i++;
}
int spfa()
{
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push(1);
v[1]=true;
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=false;
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
if(!v[j])
{
q.push(j);
v[j]=true;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(d[i]>0x3f3f3f3f/2) return -1;
ans=max(ans,d[i]);
}
return ans;
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
while (m -- )
{
int a,b,c;
cin>>a>>b>>c;
add(a, b, c);
add(b,a,c);
}
cout<<spfa();
}
农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。
当然，他将付出额外的费用在奶牛上。
农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。
他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。
给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
数据保证至少存在一个牧场和所有牛所在的牧场连通。
输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。
第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。
第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。
输出格式
共一行，输出奶牛必须行走的最小的距离和。
数据范围
1≤N≤500,
2≤P≤800,
1≤C≤1450,
1≤D≤255
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8
//spfa
#include<iostream>
using namespace std;
#include <queue>
#include<cstring>
const int N = 4000;
int d[N],v[N],id[N];
int head[N],to[N],nxt[N],w[N],i=1;
int n,m,k;
queue<int> q;
void add(int a,int b,int c)
{
to[i]=b;
w[i]=c;
nxt[i]=head[a];
head[a]=i++;
}
int spfa(int a)
{
memset(d,0x3f3f3f3f,sizeof(d));
d[a]=0;
q.push(a);
v[a]=true;
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=false;
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
if(!v[j])
{
q.push(j);
v[j]= true;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(d[id[i]]>0x3f3f3f3f/2) return 0x3f3f3f3f;
ans+=d[id[i]];
}
return ans;
}
int main()
{
cin>>n>>k>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++) cin>>id[i];
while (m -- )
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
int ans=0x3f3f3f3f;
for(int i=1;i<=k;i++)
{
ans=min(ans,spfa(i));
}
cout<< ans;
}
在 n 个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。
输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。
以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。
最后一行输入两个正整数 A,B。
数据保证 A 与 B 之间可以直接或间接地转账。
输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。
精确到小数点后 8 位。
数据范围
1≤n≤2000,
m≤105
输入样例：
3 3
1 2 1
2 3 2
1 3 3
1 3
输出样例：
103.07153164
//Floyd
#include<iostream>
#include <queue>
#include<cstring>
using namespace std;
const int N = 2e5;
int head[N],to[N],nxt[N];
double w[N];
int idx=1;
double d[N];
int v[N],n,m;
queue<int> q;
void add(int a,int b,double c)
{
to[idx]=b;
w[idx]=c;
nxt[idx]=head[a];
head[a]=idx++;
}
double spfa(int st,int ed)
{
d[st]=1.0;
q.push(st);
v[st]=true;
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=false;
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i];
if(d[j]<d[t]*w[i])
{
d[j]=d[t]*w[i];
if(!v[j])
{
q.push(j);
v[j]=true;
}
}
}
}
return d[ed];
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
while (m -- )
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,1-c*0.01);
add(b,a,1-c*0.01);
}
int s,e;
cin>>s>>e;
printf("%.8lf",100/spfa(s,e));
}
##Clear And Present Danger S
思路：floyd算法
//Floyd
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 5000;
int n, m, val[N],d[N],v[N];
int head[N], to[N], nxt[N], w[N], index1 = 0;
queue<int> q;
int route[N];
int a[N][N];
void add(int a, int b, int c)
{
to[index1] = b;
w[index1] = c;
nxt[index1] = head[a];
head[a] = index1++;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> route[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int w;
cin >> w;
a[i][j] = w;
}
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
int ans = 0;
for (int i = 1; i < m; i++)
{
ans += a[route[i]][route[i + 1]];
}
cout << ans;
}
欧拉回路问题（一笔画）
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int num[1100];
int main()
{
cin >> n >> m;
while (m--)
{
int a, b;
cin >> a >> b;
num[a]++;
num[b]++;
}
int ans = 0;
for (int i = 1; i <=1100; i++)
{
if (num[i] & 1) ans++;
}
if (ans == 0) cout << 1 << endl;
else cout << ceil(ans / 2 )<< endl;
}
欧拉回路：
若恰通过图中每条边一次回到起点,则称该回路为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图。
定理1：
一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。
一个有向图是欧拉图，当且仅当该图所有顶点度数都是0(入度与出度之和)。
定理2：
存在欧拉回路的条件：图是连通的，且不存在奇点（顶点度数为奇数）
欧拉路（此题解法 ！）
若从起点到终点的路径恰通过图中每条边一次（起点与终点是不同的点），
则该路径称为欧拉路。
定理1：
存在欧拉路的条件：图是连通的，且存在2个奇点。
如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。
思路：
统计每个点的度数，如果所有度数都是偶数，则可以一笔画出，否则需要度数为奇数的个数/2次画出
租用游艇
//floyd
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 5000;
int n, m;
int a[N][N];
int main()
{
cin >> n;
memset(a,0x3f,sizeof(a));
for (int i = 1; i < n; i++)
{
for (int j = i + 1;j <= n; j++)
{
int x;
cin >> x;
if(i==j) a[i][j]=0;
else a[i][j] = x;
}
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
cout << a[1][n];
}
Cow Party S
思路：spfa，维护两个spfa函数及两个d[N]，spfa1维护d[N]，表示从家到终点的最小距离，spfa2维护d2[N]，表示从终点到各个家中的最短距离。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 50010, M = 100010;
int n, m, st, ed, val[N], d[N], v[N], d2[N];
int head[N], to[M], nxt[M], w[M], idx = 0;
queue<int> q;
void add(int a, int b, int c)
{
to[idx] = b;
w[idx] = c;
nxt[idx] = head[a];
head[a] = idx++;
}
void spfa1(int st)
{
memset(d, 0x3f, sizeof(d));
d[st] = 0;
v[st] = true;
q.push(st);
while (!q.empty())
{
int t = q.front();
q.pop();
v[t] = false;
for (int i = head[t]; i != -1; i = nxt[i])
{
int j = to[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
if (!v[j])
{
q.push(j);
v[j] = true;
}
}
}
}
}
void spfa2(int st)
{
memset(d2, 0x3f, sizeof(d2));
d2[st] = 0;
v[st] = true;
q.push(st);
while (!q.empty())
{
int t = q.front();
q.pop();
v[t] = false;
for (int i = head[t]; i != -1; i = nxt[i])
{
int j = to[i];
if (d2[j] > d2[t] + w[i])
{
d2[j] = d2[t] + w[i];
if (!v[j])
{
q.push(j);
v[j] = true;
}
}
}
}
}
int main()
{
cin >> n >> m >> st;
memset(head, -1, sizeof(head));
while (m--)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
spfa1(st);
int ans = -1;
for (int i = 1; i <= n; i++)
{
spfa2(i);
if (d[i]+d2[st] > ans) ans = d[i]+d2[st];
}
cout << ans;
}
采购特价商品
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 500, M = 100010;
int n, m, st, ed, val[N], d[N], v[N], d2[N];
int head[N], to[M], nxt[M], w[M], idx = 0;
queue<int> q;
double a[N][N];
double getd(double x1, double y1,double x2,double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
struct e
{
int x,y;
}edge[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
edge[i].x = x;
edge[i].y = y;
}
cin >> m;
memset(a,0x7f,sizeof(a));
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
a[y][x] = min(a[y][x],getd(edge[x].x, edge[x].y, edge[y].x, edge[y].y));
a[x][y] = min(a[x][y],getd(edge[x].x, edge[x].y, edge[y].x, edge[y].y));
}
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
cin >> st >> ed;
printf("%.2lf", a[st][ed]);
}
prim算法
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 550;
int a[N][N],v[N],n,m,d[N];
int prim()
{
memset(d,0x3f,sizeof(d));
int ans=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!v[j]&&(t==-1||d[t]>d[j]))
{
t=j;
}
}
if(i!=1&&d[t]==0x3f3f3f3f) return 0x3f3f3f3f;
if(i!=1) ans+=d[t];
for(int j=1;j<=n;j++)
{
d[j]=min(d[j],a[t][j]);
}
v[t]=true;
}
return ans;
}
int main()
{
cin>>n>>m;
memset(a,0x3f,sizeof(a));
while (m -- )
{
int x,y,z;
cin>>x>>y>>z;
a[x][y]=a[y][x]=min(a[x][y],z);
}
int ans=prim();
if(ans==0x3f3f3f3f) cout << "impossible"<<endl;
else cout<<ans<<endl;
}
kruskal算法
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 203000;
int a[N],n,m;
struct e
{
int u,v, w;
bool operator<(const e& aa)
{
return w<aa.w;
}
}edge[N];
int find(int x)
{
if(x!=a[x]) a[x]=find(a[x]);
return a[x];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
edge[i].u=x;
edge[i].v=y;
edge[i].w=z;
}
sort(edge,edge+m);
for(int i=1;i<=n;i++)
{
a[i]=i;
}
int ans=0,cnt=0;
for(int i=0;i<m;i++)
{
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
int x=find(u),y=find(v);
if(x!=y)
{
a[x]=y;
ans+=w;
cnt++;
}
}
if(cnt<n-1) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,dp[N],a[N],ans,g[N];
int main()
{
while(cin>>a[n]) n++;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[j]>=a[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
ans=0;
for(int i=0;i<n;i++)
{
int k=0;
while(k<ans &&g[k]<a[i]) k++;
g[k]=a[i];
if(k>=ans) ans++;
}
cout<<ans;
}
繁忙的都市
最小生成树问题
//kruskal算法
#include<bits/stdc++.h>
using namespace std;
const int N = 11010;
int n,a[N],m,ans=0;
int f[N];
struct e
{
int u,v,w;
bool operator < (const e &rhs) const
{
return w < rhs.w;
}
}edge[N];
int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void join(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) f[x]=y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
edge[i].u=x;
edge[i].v=y;
edge[i].w=z;
}
//kruskal
sort(edge+1,edge+m+1);
for(int i=1;i<=n;i++)
{
f[i]=i;
}
int cnt=0;
for(int i=1;i<=m;i++)
{
int x=find(edge[i].u);
int y=find(edge[i].v);
if(x!=y)
{
join(x,y);
cnt++;
ans=edge[i].w;
if(cnt==n-1) break;
}
}
cout<<n-1<<" "<<ans<<endl;
}
营救
题目背景
“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……
题目描述
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 tt 区，而自己在 ss 区。
该市有 mm 条大道连接 nn 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线，使得经过道路的拥挤度最大值最小。
输入格式
第一行有四个用空格隔开的 nn，mm，ss，tt，其含义见【题目描述】。
接下来 mm 行，每行三个整数 u, v, wu,v,w，表示有一条大道连接区 uu 和区 vv，且拥挤度为 ww。
两个区之间可能存在多条大道。
输出格式
输出一行一个整数，代表最大的拥挤度。
思路：最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,m,s,t;
int p[N];
struct e
{
int u,v,w;
bool operator <(const e &a) const
{
return w<a.w;
}
}edge[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void join(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy) p[xx]=yy;
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
edge[i]={x,y,z};
}
sort(edge+1,edge+1+m);
for(int i=1;i<=n;i++)
{
p[i]=i;
}
for(int i=1;i<=m;i++)
{
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(find(u)!=find(v))
{
join(u,v);
}
if(find(s)==find(t)) //特判起点到终点
{
cout<<w;
break;
}
}
}
回家
#include<bits/stdc++.h>
using namespace std;
const int N=2501,M=2600000;
int n,m,v[M];
int a[200][200];
int main()
{
cin>>n;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++)
{
char x,y;
int z;
cin>>x>>y>>z;
int xx=(int)x;
int yy=(int)y;
a[xx][yy]=a[yy][xx]=min(a[xx][yy],z);
}
for(int k=1;k<=122;k++)
{
for(int i=1;i<=122;i++)
{
for(int j=1;j<=122;j++)
{
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
char ii;
int ans=0x3f3f3f3f;
for(int i='A';i<='Y';i++)
{
if(a[i]['Z']<ans)
{
ii=i;
ans=a[i]['Z'];
}
}
cout<<ii<<" "<<ans;
}
Building Roads S
#include<bits/stdc++.h>
using namespace std;
const int N=10000100;
int n,m;
typedef pair<int,int> PII;
queue<int> q;
pair<double,double> p[N];
int pp[N];
double getd(int x1,int y1,int x2,int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
struct e
{
long long u,v;
long double w;
bool operator<(const e& aa)
{
return w<aa.w;
}
}edge[N];
int find(int x)
{
if(pp[x]!=x) pp[x]=find(pp[x]);
return pp[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) pp[i]=i;
for(int i=1;i<=n;i++)
{
cin>>p[i].first>>p[i].second;
}
int cnt=0;
//cnt要从0开始，然后++cnt,不能从1开始cnt++
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int x1=p[i].first,y1=p[i].second;
int x2=p[j].first,y2=p[j].second;
edge[++cnt].u=i;
edge[cnt].v=j;
edge[cnt].w=sqrt((double)(x1-x2)*(double)(x1-x2)+(double)(y1-y2)*(double)(y1-y2));
}
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
edge[++cnt].u=x;
edge[cnt].v=y;
edge[cnt].w=0.0;
}
sort(edge+1,edge+1+cnt);
double ans=0.0;
for(int i=1;i<=cnt;i++)
{
int x=find(edge[i].u);
int y=find(edge[i].v);
if(x!=y)
{
pp[y]=x;
ans+=edge[i].w;
}
}
printf("%.2lf",ans);
}
邮递员送信（正反迪杰斯特拉）
思路：
根据时间复杂度，可以用迪杰斯特拉算法。
正常的迪杰斯特拉算法是其他点到1号点的最短路
可以建立一个反向图，使用迪杰斯特拉算法，求和即可
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],v[N],d[N],n,m; //此列为正向迪杰斯特拉
int b[N][N],d2[N],v2[N]; //此列为反向迪杰斯特拉
void dijkstra(int s)
{
memset(d,0x3f,sizeof(d));
d[s]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!v[j]&&(t==-1||d[t]>d[j]))
{
t=j;
}
}
v[t]=true;
for(int j=1;j<=n;j++)
{
d[j]=min(d[j],d[t]+a[t][j]);
}
}
}
void dijkstra2(int s)
{
memset(d2,0x3f,sizeof(d2));
d2[s]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!v2[j]&&(t==-1||d2[t]>d2[j]))
{
t=j;
}
}
v2[t]=true;
for(int j=1;j<=n;j++)
{
d2[j]=min(d2[j],d2[t]+b[t][j]);
}
}
}
int main()
{
cin>>n>>m;
memset(a,0x3f,sizeof(a));
memset(b,0x3f,sizeof(b));
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x][y]=min(a[x][y],z);
b[y][x]=min(b[y][x],z);
}
dijkstra(1);
dijkstra2(1);
int ans=0;
for(int i=2;i<=n;i++)
{
ans+=d[i];
ans+=d2[i];
}
cout<<ans;
}
营救
题目背景
“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……
题目描述
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 tt 区，而自己在 ss 区。
该市有 mm 条大道连接 nn 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线，使得经过道路的拥挤度最大值最小。
输入格式
第一行有四个用空格隔开的 nn，mm，ss，tt，其含义见【题目描述】。
接下来 mm 行，每行三个整数 u, v, wu,v,w，表示有一条大道连接区 uu 和区 vv，且拥挤度为 ww。
两个区之间可能存在多条大道。
输出格式
输出一行一个整数，代表最大的拥挤度。
思路：最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,m,s,t;
int p[N];
struct e
{
int u,v,w;
bool operator <(const e &a) const
{
return w<a.w;
}
}edge[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void join(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx!=yy) p[xx]=yy;
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
edge[i]={x,y,z};
}
sort(edge+1,edge+1+m);
for(int i=1;i<=n;i++)
{
p[i]=i;
}
for(int i=1;i<=m;i++)
{
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(find(u)!=find(v))
{
join(u,v);
}
if(find(s)==find(t)) //特判起点到终点
{
cout<<w;
break;
}
}
}
Q.E.D.