pan 静下心 logs sin tin ace sca !=
个人心得:周测的时候心情有点闷,看到就不想去做,比完后第二天拿着一做,这么简单,我也是醉了。
虽然最后一周了,但是我还是希望你能稳住别被其他事扰乱军心了,希望以后的你能够静下心去思考。
这题:就是用 Kruskal 算法第一遍找出最大值中的最小值,第二次再反过来用一次就好了。
这样阴沉的天气持续下去,我们不免担心起他的健康。
Input 两个正整数 N,M。(1 <= N <= 10^5, N <= M <= 2 * 10^5)
接下来 M 行,每一行有三个整数 A, B, V。(1 <= A, B <= N, INT_MIN <= V <= INT_MAX)
保证输入数据合法。Output 输出一个正整数 R,表示符合条件的魔法阵的魔力值之和。Sample Input
- 4 6
- 1 2 3
- 1 3 1
- 1 4 7
- 2 3 4
- 2 4 5
- 3 4 6
Sample Output
- 12
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int magic[100005];
- int n,m;
- struct power
- {
- int u,v,q;
- }p[100005*2];
- bool cmp(power a,power b){
- return a.q<b.q;
- }
- void init()
- {
- for(int i=1;i<=n;i++)
- magic[i]=i;
- }
- int getm(int x){
- if(x!=magic[x])
- magic[x]=getm(magic[x]);
- return magic[x];
- }
- void marge(int x,int y){
- int p=getm(x),q=getm(y);
- if(p!=q)
- magic[p]=q;
- }
- int main(){
- scanf("%d%d",&n,&m);
- init();
- for(int i=1;i<=m;i++)
- scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].q);
- sort(p+1,p+m+1,cmp);
- int maxn=0;
- long long oo=0;
- int flag=0;
- for(int i=1;i<=m;i++){
- if(getm(p[i].u)==getm(p[i].v)) continue;
- marge(p[i].u,p[i].v);
- if(maxn<p[i].q)
- {
- maxn=p[i].q;
- flag=i;
- }
- }
- init();
- for(int i=m;i>=1;i--)
- {
- if(p[i].q>maxn) continue;
- if(getm(p[i].u)==getm(p[i].v)) continue;
- marge(p[i].u,p[i].v);
- oo+=p[i].q;
- }
- printf("%lld\n",oo);
- return 0;
- }
魔法跳舞链 (最小生成树)
来源: http://www.bubuko.com/infodetail-2272805.html