上午把P1629 邮递员写了一封信。我在哔哩哔哩看了两种小生成路的动态解释。
P1629 邮递员送信
题目描述
有一个邮递员东西，邮局在节点 11.他总共要送 n-1n?1 样品的目的地是节点 22 到节点 nn。由于城市交通繁忙，所有道路都是单行的，共有的 mm 一条路。邮递员每次只能带一件东西，而且。求送完这 n-1n?1 样东西并且至少需要时间。
输入格式
第一行包括两个整数，nn 和 mm，表示城市节点和道路的数量。
第二行到第 (m 1)(m 1) 行，每行三个整数，u,v,wu,v,w，表示从 uu 到 vv 通过时间有一个 ww 的道路。
输出格式
输出只有一行，包括一个整数，至少需要时间。
输入输出样例
复制
5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2
复制
83
说明/提示
对于 30\0% 的数据，1 \leq n \leq 2001≤n≤200。
对于 100\0% 的数据，1 \leq n \leq 10^31≤n≤103，1 \leq m \leq 10^51≤m≤105，1\leq u,v \leq n1≤u,v≤n，1 \leq w \leq 10^41≤w≤104，输入保证任意两点都能互相到达。
想法：邮递员每次都会带一封电子邮件到相应的点，这是迪杰斯特拉找到的最小点，但这条路不一定是最短的。所以反向使用它dij。
代码实现：
#include<bits/stdc .h> using namespace std; int n,m; int dvis[1000000]; int fvis[1000000]; int dlow[1000000]; int flow[1000000]; int maxm=1e9; struct edge{ int to; int v; int next; }dmp[100000],fmp[100000]; int dhead[1000000]; int fhead[1000000]; struct node { int dis; int v; bool operator <(const node &x) const { return x.v<v; } }; int cnt=0; void add(int a,int b,int v) { cnt ; dmp[cnt].to=b; dmp[cnt].v=v; dmp[cnt].next=dhead[a]; dhead[a]=cnt; fmp[cnt].to=a; fmp[cnt].v=v; fmp[cnt].next=fhead[b]; fhead[b]=cnt; } void dij() { priority_queue<node>q; for(int i=1;i<=n;i ) dlow[i]=maxm; dlow[1]=0; q.push((node){1,0}); while(q.size()!=0) { node x=q.top(); q.pop(); int dis=x.dis; if(dvis[dis]==1) continue; dvis[dis]=1; for(int i=dhead[dis];i!=0;i=dmp[i].next) { int t=dmp[i].to; if(dlow[t]>dlow[dis] dmp[i].v) { dlow[t]=dlow[dis] dmp[i].v; q.push((node){t,dlow[t]}); } } } } void fdij() { for(int i=1;i<=n;i ) flow[i]=maxm; flow[1]=0; priority_queue<node>q; q.push((node){1,0}); while(q.size()!=0) { node x=q.top(); q.pop(); int dis=x.dis; if(fvis[dis]==1) continue; fvis[dis]=1; for(int i=fhead[dis];i!=0;i=fmp[i].next) { int t=fmp[i].to; if(flow[t]>flow[dis] fmp[i].v) { flow[t]=flow[dis] fmp[i].v; q.push((node){t,flow[t]}); } } } } int main() { cin>>n>>m; int a,b,v; for(int i=1;i<=m;i ) { cin>>a>>b>>v; add(a,b,v); } dij(); fdij(); int sum=0; for(int i=2;i<=n;i ) { sum=sum dlow[i] flow[i]; } cout<<sum; } 这里dlow，dhead表示来的时候，flow，fhead表示回来。
下午学习了最小生成树Kruskal写作方法。这个算法是从小到大对路劲进行排序，然后一个接一个地取，以确保没有环。如果形成一个环，则不需要连接这条路。知道一切都结束了。
晚上，模板问题完成了
P3366 模板最小生成树
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
样例解释：
因此，最小生成树的总边权是2 2 3=72 2 3=7。
思路：运用Kruskal 算法。
代码实现：
#include<bits/stdc .h> using namespace std; int n,m; struct node{ int a;//起点 int b;//终点 int v;//距离 }mp[200010]; int father[5001]; bool compare(node a,node b) { return a.v<b.v; } int find_root(int n) { if(father[n]==n) return father[n]; else return find_root(father[n]); } void k() { int flag=0; sort(mp,mp m,compare); int cnt=0; int sum=0; for(int i=0;i<m;i ) { int a=find_root(mp[i].a); int b=find_root(mp[i].b); if(a!=b) { sum =mp[i].v; father[b]=a; cnt ; } if(cnt==n-1) { flag=1; break; } } if(flag==0) cout<<"orz"; else if(flag==1) cout<<sum; } int main() { cin>>n>>m; for(int i=1;i<=n;i ) father[i]=i; int a,b,v; for(int i=0;i<m;i ) { cin>>a>>b>>v; mp[i].a=a; mp[i].b=b; mp[i].v=v; } k(); } 明天学习prim写法。
/p>