Nasa, being the most talented programmer of his time, can’t think things to be so simple. Recently all his neighbors have decided to connect themselves over a network (actually all of them want to share a broadband internet connection :-)). But he wants to minimize the total cost of cable required as he is a bit fastidious about the expenditure of the project. For some unknown reasons, he also wants a second way left. I mean, he wants to know the second best cost (if there is any which may be same as the best cost) for the project. I am sure, he is capable of solving the problem. But he is very busy with his private affairs(?) and he will remain so. So, it is your turn to prove yourself a good programmer. Take the challenge (if you are brave enough)...
Input
Input starts with an integer t ≤ 1000 which denotes the number of test cases to handle. Then follows t datasets where every dataset starts with a pair of integers v (1 ≤ v ≤ 100) and e (0 ≤ e ≤ 200). v denotes the number of neighbors and e denotes the number of allowed direct connections among them. The following e lines contain the description of the allowed direct connections where each line is of the form ‘start end cost’, where start and end are the two ends of the connection and cost is the cost for the connection. All connections are bi-directional and there may be multiple connections between two ends.
Output
There may be three cases in the output
1. No way to complete the task,
2. There is only one way to complete the task,
3. There are more than one way.
Output ‘No way’ for the first case, ‘No second way’ for the second case and an integer c for the third case where c is the second best cost. Output for a case should start in a new line.
Sample Input
4
5 4
1 2 5
3 2 5
4 2 5
5 4 5
5 3
1 2 5
3 2 5
5 4 5
5 5
1 2 5
3 2 5
4 2 5
5 4 5
4 5 6
1 0
Sample Output
Case #1 : No second way
Case#2 : No way
Case #3 : 21
Case #4 : No second way
题意：有一些点和一些边，问花费最小的值能否这些边能否将这些点连在一起，有没有第二种连接方案，注意这些边有一些边是重边。对于输出，如果不能连在一起则输出"No way",如果没有第二种让他们连在一起的方案则输出"No second way",如果有第二种方案则输出第二种方案的值。
思路：最小生成树和次小生成树的存在和求值问题，比较简单，由于有重边的情况因此不适合用prim算法，适合用Kruskal算法。具体思路见代码
代码：
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 struct node 22 { 23 //x,y表示边的左右端点，value表示边的值 24 int x,y,value; 25 //flag标记边是否在树上 26 bool flag; 27 }no[205]; 28 //n表示点数,m表示边数 29 int n,m; 30 //fa表示树上的顶点 31 int fa[105]; 32 //ve用于与第i个点有连接的点 33 vector<int> ve[105]; 34 //maxn存放两点之间的最大值 35 int maxn[105][105]; 36 //初始化 37 void init() 38 { 39 //开始时与自己相连的只有自己，同时顶点也是自己 40 for(int i=0;i<=n;i++) 41 { 42 ve[i].clear(); 43 ve[i].push_back(i); 44 fa[i]=i; 45 } 46 } 47 //查找顶点 48 int find(int x) 49 { 50 //如果找到顶点，则返回 51 if(fa[x]==x) 52 { 53 return x; 54 } 55 //递归查找x的上一个点的上一个点，同时压缩路径 56 return fa[x]=find(fa[x]); 57 } 58 //排序,按边的值从小到大 59 bool cmp(node a,node b) 60 { 61 return a.value<b.value; 62 } 63 //最小生成树Kruskal算法 64 int kruskal() 65 { 66 //对边进行排序 67 sort(no+1,no+m+1,cmp); 68 //初始化数据 69 init(); 70 //ans表示最小生成树的权值和,cnt表示已经连接的边数 71 int ans=0,cnt=0; 72 //遍历所有边 73 for(int i=1;i<=m;i++) 74 { 75 //如果连接了n-1个边，则表示已经连接所有的点了 76 if(cnt==n-1) 77 { 78 break; 79 } 80 //记录当前边的两边端点的顶点 81 int fx=find(no[i].x),fy=find(no[i].y); 82 //如果他们不相等则进行操作 83 if(fx!=fy) 84 { 85 //将fx的顶点变成fy，相当于把fx这个树的顶点挂在fy这个树顶的下面 86 fa[fx]=fy; 87 //生成树的边数加1 88 cnt++; 89 //加上这个边的权值 90 ans+=no[i].value; 91 //标记这个边 92 no[i].flag=true; 93 //对fx，fy则两颗树的所有点遍历 94 for(int j=0;j<ve[fx].size();j++) 95 { 96 for(int k=0;k<ve[fy].size();k++) 97 { 98 //将这两可树的所有点之间的最大值都变成现在变的值 99 //由于对no进行过排序，因此此时no[i].value的值是这个树上的最大值 100 maxn[ve[fx][j]][ve[fy][k]]=maxn[ve[fy][k]][ve[fx][j]]=no[i].value; 101 } 102 } 103 //对fx的树遍历，将fx树上的点都连在fy树上 104 for(int j=0;j<ve[fx].size();j++) 105 { 106 ve[fy].push_back(ve[fx][j]); 107 } 108 } 109 } 110 //如果连了n-1条边则表示有最小生成树 111 if(cnt==n-1) 112 { 113 return ans; 114 } 115 else 116 { 117 return -1; 118 } 119 } 120 //次小生成树，mst表示最小生成树的权值和 121 int second_kruskal(int mst) 122 { 123 int ans=INF; 124 //遍历所有边 125 for(int i=1;i<=m;i++) 126 { 127 //如果这个边不在最小生成树上 128 if(!no[i].flag) 129 { 130 //计算最小生成树加外边在减内边否的最小值 131 ans=min(ans,mst+no[i].value-maxn[no[i].x][no[i].y]); 132 } 133 } 134 return ans; 135 } 136 137 int main() 138 { 139 int t,ans=1; 140 scanf("%d",&t); 141 while(t--) 142 { 143 scanf("%d %d",&n,&m); 144 for(int i=1;i<=m;i++) 145 { 146 scanf("%d %d %d",&no[i].x,&no[i].y,&no[i].value); 147 no[i].flag=0; 148 } 149 printf("Case #%d : ",ans++); 150 int s1=kruskal(); 151 if(s1==-1) 152 { 153 printf("No way "); 154 } 155 else if(m>n-1) 156 { 157 printf("%d ",second_kruskal(s1)); 158 }else 159 { 160 printf("No second way "); 161 } 162 } 163 }