描述
东汉建安十三年,孙权、刘备联军在长江赤壁一带,大败曹操军队的一次决战。曹操败袁绍、破乌桓,基本统一北方后,于建安十三年七月,自宛挥师南下,欲先灭刘表,再顺长江东进,击败孙权,以统一天下。九月,曹军进占新野,时刘表已死,其子刘琮不战而降。依附刘表屯兵樊城的刘备仓促率军民南撤。曹操
收编刘表部众,号称八十万大军向长江推进。刘备在长被曹军大败后,于退军途中派诸葛亮赴柴桑会见孙权,说服孙权结盟抗曹。
孙权命周瑜为主将,程普为副,率三万精锐水军,联合屯驻樊口的刘备军,共约五万人溯长江西进,迎击曹军。十一月,孙刘联军与曹军对峙于赤壁。曹操将战船首尾相连,结为一体,以利演练水军,伺机攻战。周瑜采纳部将黄盖所献火攻计,并令其致书曹操诈降,曹操中计。黄盖择时率蒙冲斗舰乘风驶入曹军水寨纵火。曹军船阵被烧,火势延及岸上营寨,孙刘联军乘势出击,曹军死伤过半,遂率部北退,留征南将军曹仁固守江陵。联军乘胜扩张战果,孙刘两军分占荆州要地。
赤壁决战,曹操在有利形势下,轻敌自负,指挥失误,终致战败。孙权、刘备在强敌进逼关头,结盟抗战,扬水战之长,巧用火攻,终以弱胜强。
赤壁之战结束之后魏蜀吴三国决定握手求和,但是因为之前四处交战,把道路全部毁坏了,现在需要重新修路使得三国的国都能够连通.诸葛亮是这个项目的负责人,但是他太聪明了,对于这种题目都懒得思考了,于是就交给你了。
输入
输入一个 T(T ≤ 30)表示 T 组数据
对于每组数据,输入两个正整数 n,m (n<=10000,m<=30000)表示 n 个城市和 m 条可修建的路。
接下来m行,每行输入三个整数ai,bi,ci 表示从ai到bi (1<=ai,bi<=n)的道路需要 ci(1<=ci<=500)的时间进行修建(同一时间只能有一条道路在修建中)。
接下来输入三个整数 A,B,C(1<=A,B,C<=n A,B,C 互不相等) 分别表示三国国都所在的城市。
输出
对于每组数据,输出一个整数,表示所需要的时间。如果无解输入-1。
样例输入
1
4 5
1 2 1
1 3 1
1 4 1
2 3 2
3 4 2
1 2 3
样例输出
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e4+10; 4 struct node{ 5 int x,z,y; 6 }; 7 node a[30005]; 8 vector<pair<int,int> >g[N]; 9 int vis[N],dis[N],f[N]; 10 int n,m; 11 bool cmp(node a,node b) 12 { 13 return a.z<b.z; 14 } 15 int find(int x) 16 { 17 if(f[x]!=x)f[x] = find(f[x]); 18 return f[x]; 19 } 20 void merger(int x,int y) 21 { 22 f[y] = x; 23 } 24 int main() 25 { 26 int t; 27 cin>>t; 28 while(t--) 29 { 30 scanf("%d %d",&n,&m); 31 for(int i=1;i<=m;i++)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z); 32 sort(a+1,a+1+m,cmp); 33 int sum = 0; 34 for(int i=1;i<=m;i++) 35 { 36 int f1 = find(a[i].x); 37 int f2 = find(a[i].y); 38 if(f1!=f2) 39 { 40 sum++; 41 g[a[i].x].push_back(make_pair(a[i].y,a[i].z)); 42 g[a[i].y].push_back(make_pair(a[i].x,a[i].z)); 43 merger(f1,f2); 44 if(sum==n-1)break; 45 } 46 } 47 int A,B,C; 48 cin>>A>>B>>C; 49 int k1 = find(A),k2 = find(B),k3 = find(C); 50 if(k1==k2&&k2==k3) 51 { 52 //请继续 53 } 54 } 55 return 0; 56 }