关键路径没有写！！！！
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define MAX 1010
//MST-kruskal
int m;
int par[1010];
void init(int k){
for(int i=0;i<k;i++){
par[i]=i;
}
}
int findset(int x){
if(par[x]==x)return x;
par[x]=findset(par[x]);
return par[x];
}
void join(int x,int y){
int s=findset(par[x]);
int t=findset(par[y]);
if(par[x]!=par[y])par[s]=t;
}
bool same(int x,int y){
return findset(x)==findset(y);
}
struct edge{int u,v,w;};
bool cmp(const edge &a,const edge &b){
return a.w<b.w;
}
edge es[1010];
void kruskal(){
int sum=0;
sort(es,es+m,cmp);
init(m+10);
printf("最小生成树如下\n");
for(int i=0;i<m;i++){
edge e=es[i];
// cout<<e.u<<e.v<<e.w<<endl;
if(!same(e.u,e.v)){
join(e.u,e.v);
sum+=e.w;
printf("%d - %d\n",e.u,e.v);
}
}
printf("路径总和：%d\n",sum);
}
void fun_1(){
printf("请输入边数：\n");
cin>>m;
for(int i=0;i<m;i++){
cin>>es[i].u>>es[i].v>>es[i].w;
}
kruskal();
}
//constructing
//关键路径
stack<int>stack2;
int indegree[MAX];
struct node2{
int adjvex;
node2 *next;
}adj[MAX];
int create(int V,int E){//create graph
node2 *p;
for(int i=1;i<=V;i++){//init Vex
adj[i].adjvex=i;
adj[i].next=NULL;
}
cout<<"请输入"<<E<<"条边:"<<endl;
for(int i=1;i<=E;i++){//int edge
int v2,u2;
cin>>u2>>v2;
p=new node2;//与 malloc 类似
p->adjvex=v2;
p->next=adj[u2].next;
adj[u2].next=p;
}
return 1;
}
void print2(int n2)//邻接表打印函数
{
int i;
node2 *p;
for(i=1;i<=n2;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->adjvex;
if(p->next!=NULL)
cout<<"->";
p=p->next;
}
cout<<endl;
}
}
void topsort(int n){
node2 *p;
memset(indegree,0,sizeof(indegree));
for(int i=1;i<=n;i++){// 求入度 没有前驱的点
p=adj[i].next;
while(p){
indegree[p->adjvex]++;
p=p->next;
}
}
for(int i=1;i<=n;i++){// 没有前驱的点入栈
if(indegree[i]==0){
stack2.push(i);
}
}
int cnt=0;
cout<<"拓扑排序： ";
while(!stack2.empty()){
int t=stack2.top();
stack2.pop();
cout<<t<<"->";
cnt++;
p=adj[t].next;
while(p){
int k=p->adjvex;//去除与t相连的弧
indegree[k]--;
if(indegree[k]==0)
stack2.push(k);
p=p->next;
}
}
cout<<endl;
if(cnt<n)cout<<"图中有环"<<endl;
}
void fun_2(){
int n2;
int m2;
cout<<"请输入顶点数及边数:";
cin>>n2>>m2;
create(n2,m2);
cout<<"输入的邻接表为:"<<endl;
print2(n2);
cout<<"拓扑排序结果为:"<<endl;
topsort(n2);
}
void fun_3(){
}
//单源最短路 floyd / Dijkstra
int dist[1010][1010];
int path[1010][1010];
int n1,k1;
void init_dist_path(){
for(int i=1;i<=n1;i++){
for(int j=1;j<=n1;j++){
dist[i][j]=INF;
path[i][j]=j;
}
}
}
void floyd(){
for(int k=1;k<=n1;k++){
for(int i=1;i<=n1;i++){
for(int j=1;j<=n1;j++){
if(dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[i][k];
}
}
}
}
}
void print_path(int u,int v){
int tmp=u;
printf("%d",u);
while(tmp!=v)
{
printf("->%d",path[tmp][v]);
tmp=path[tmp][v];
}
}
/*
void fun_4(){
printf("请输入顶点数与路径数：\n");
cin>>n1>>k1;
init_dist_path();
for(int i=1;i<=k1;i++){
int s,t,d;
cin>>s>>t>>d;
dist[s][t]=d;
dist[t][s]=d;
}
floyd();
int s,t;
cin>>s>>t;
printf("路径如下：\n");
print_path(s,t);
printf("\n");
printf("最短路长： ");
printf("%d\n",dist[s][t]);
}
*/
int ne,nv;
struct Edge{
int from,to,weight;
Edge(int u,int v,int w):from(u),to(v),weight(w){};
};
struct Node{
int id,w;
friend bool operator <(const Node a,const Node b){
return a.w>b.w;
}
};
vector<Edge>E;
vector<int>G[1010];
int dist_4[1010],pre_4[1010];
void add_edge(int u,int v,int w){
E.push_back(Edge(u,v,w));
G[u].push_back((int)E.size()-1);
}
void dijkstra(int s){
priority_queue<Node> que;
memset(dist_4,INF,sizeof(dist_4));
dist_4[s]=0;
que.push(Node{s,0});
while(!que.empty()){
Node p=que.top();
que.pop();
int u=p.id,d=p.w;
if(dist_4[u]<d)continue;
for(int i=0;i<G[u].size();i++){
int e=G[u][i];
int v=E[e].to;
if(dist_4[v]>dist_4[u]+E[e].weight){
dist_4[v]=dist_4[u]+E[e].weight;
que.push(Node{v,dist_4[v]});
pre_4[v]=u;
}
}
}
}
void get_path(int ed){
if(pre_4[ed])get_path(pre_4[ed]);
else return;
cout<<pre_4[ed]<<"->";
}
void fun_4(){
cout<<"输入顶点与边数："<<endl;
cin>>nv>>ne;
for(int i=0;i<ne;i++){
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
}
int s;
cout<<"输入起点"<<endl;
cin>>s;
dijkstra(s);
printf("最短路如下：\n");
for(int i=0;i<nv;i++){//i=1,i<=nv
if(i==s)continue;
printf("0 => %d :(权值和：%d)",i,dist_4[i]);
cout<<" 0->";
get_path(i);
cout<<i<<endl;
}
}
//
int main(){
int choice;
do{
printf("功能： 1.MST 2.拓扑排序 3.关键路径 4.单源最短路 0.Exit\n");
cin>>choice;
switch(choice){
case 1: fun_1();break;
case 2: fun_2();break;
case 3: fun_3();break;
case 4: fun_4();break;
case 0: break;
default :printf("输入有误！\n");
}
}while(choice);
return 0;
}
/*
测试数据：
1.
11
1 2 7
1 4 5
2 4 9
2 3 8
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11
2.
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
3.
4.
5 7
0 1 100
0 2 30
0 4 10
2 1 60
2 3 60
3 1 10
4 3 50
*/