html5手机网站开发视频教程,中国执行信息公开网查询,wordpress搬家换域名不换服务器,芜湖做网站推广有哪些公司正题
就是给出一个无向图#xff0c;求最小环。 输入输出#xff08;需要自取#xff09;
Input
每组数据的第一行包含两个正整数#xff1a;十字路口的个数N(N100)#xff0c;另一个是道路的 数目M(M10000)。接下来的每一行描述一条路#xff1a;每一行有三个…正题
就是给出一个无向图求最小环。 输入输出需要自取
Input
每组数据的第一行包含两个正整数十字路口的个数N(N100)另一个是道路的 数目M(M10000)。接下来的每一行描述一条路每一行有三个正整数这条路连接的两个路口的编号以及这条路的长度小于500的正整数。
Output 每一行输出都是一个答案。如果这条观光路线是不存在的话就显示“No solution”或者输出这条最短路线的长度。
Sample Input
样例
5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20
样例2
4 3 1 2 10 1 3 20 1 4 30 -1
Sample Output
样例
61
样例2
No solution 解题1:Floyd算法
就是一个Floyd算法然后在中间统计一下最小环。
代码Floyd
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,m,a[101][101],dis[101][101],ans,from,to,lon;
int main()
{scanf(%d%d,n,m);memset(a,127/3,sizeof(a));memset(dis,127/3,sizeof(dis));for (int i1;im;i){scanf(%d%d%d,from,to,lon);a[from][to]lon;a[to][from]lon;//记录距离dis[from][to]lon;dis[to][from]lon;//记录最短路}ans707406377;for (int k1;kn;k){for (int i1;in;i)for (int ji1;jn;j)if (dis[i][j]!dis[0][0])ansmin(ans,dis[i][j]a[i][k]a[k][j]);//更新最小环for (int i1;in;i)for (int j1;jn;j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);//更新最短路}if (ans707406377) printf(No solution);else printf(%d,ans);
}
当然也可以进行优化当k没有枚举到这个点时那么后面的都没有被算出来而且这是个无向图
代码Floyd优化
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,m,a[101][101],dis[101][101],ans,from,to,lon;
int main()
{scanf(%d%d,n,m);memset(a,127/3,sizeof(a));memset(dis,127/3,sizeof(dis));for (int i1;im;i){scanf(%d%d%d,from,to,lon);a[from][to]lon;a[to][from]lon;dis[from][to]lon;dis[to][from]lon;}ans707406377;for (int k1;kn;k){for (int i1;ik;i)for (int ji1;jk;j)if (dis[i][j]!dis[0][0])ansmin(ans,dis[i][j]a[i][k]a[k][j]);for (int i1;in;i)for (int j1;jn;j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}if (ans707406377) printf(No solution);else printf(%d,ans);
} 解题2:dijkstra
枚举边然后删去那条边然后求那条边头尾最短路接下来恢复那条边加上那条边的权值就是一个环的长度。
代码dijkstra
#includecstdio
#includeiostream
#includecstring
using namespace std;
int w,minl,n,m,a[101][101],c[101],ans,from,to,lon,l[10001][2],mn,s;
bool b[101];
int main()
{scanf(%d%d,n,m);mn0;memset(a,127/3,sizeof(a));for (int i1;im;i){scanf(%d%d%d,from,to,lon);a[from][to]lon;a[to][from]lon;l[mn][0]from;l[mn][1]to;//记录边}ans707406377;for (int k1;kmn;k){int oa[l[k][0]][l[k][1]];a[l[k][0]][l[k][1]]707406378;a[l[k][1]][l[k][0]]707406378;//删边sl[k][0];for (int i1;in;i) c[i]a[s][i];memset(b,false,sizeof(b));b[s]true;c[s]0;for (int i1;in;i){minl707406377;w0;for (int j1;jn;j)if (!b[j] c[j]minl){minlc[j];wj;}if (w0) break;b[w]true;for (int j1;jn;j)if (c[w]a[w][j]c[j])c[j]c[w]a[w ][j];}//以上dij不解释ansmin(ans,c[l[k][1]]o);//求该环长度a[l[k][0]][l[k][1]]o;//恢复两条边a[l[k][1]][l[k][0]]o;}if (ans707406377) printf(No solution);else printf(%d,ans);
}
