P1396 营救

题目背景

“咚咚咚……”“查水表”原来是查水表来了现在哪里找这么热心上门的查表员啊小明感动得热泪盈眶开起了门……

题目描述

妈妈下班回家街坊邻居说小明被一群陌生人强行押上了警车妈妈丰富的经验告诉她小明被带到了 tt 区而自己在 ss 区。

该市有 mm 条大道连接 nn 个区一条大道将两个区相连接每个大道有一个拥挤度。小明的妈妈虽然很着急但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 nnmmsstt其含义见【题目描述】。

接下来 mm 行每行三个整数 u, v, wu,v,w表示有一条大道连接区 uu 和区 vv且拥挤度为 ww。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数代表最大的拥挤度。

输入输出样例

输入 #1复制

3 3 1 3

1 2 2

2 3 1

1 3 3

输出 #1复制

2

说明/提示

数据规模与约定

• 对于 30\%30% 的数据保证 n\leq 10n≤10。

• 对于 60\%60% 的数据保证 n\leq 100n≤100。

• 对于 100\%100% 的数据保证 1 \leq n\leq 10^41≤n≤1041 \leq m \leq 2 \times 10^41≤m≤2×104w \leq 10^4w≤1041 \leq s, t \leq n1≤s,t≤n。且从 ss 出发一定能到达 tt 区。

---

样例输入输出 1 解释

小明的妈妈要从 1 号点去 3号点最优路线为 1->2->3。

思路最小生成树模板题判断条件改动一下即可当s和t联通即得到营救成功

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define inf 99999999
struct node
{
    int u,v,w;
}e[20005];
int f[10005];
int cmp(const void*p1,const void *p2)//快速排序的回调函数
{
     return ((struct node *)p1)->w-((struct node *)p2)->w;
}
//并查集
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
        f[i]=i;
    }
}
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
} 
int cb(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        f[x]=y;
        
        return 1;
    }
    return 0;
}
//主函数
int main()
{
    int n,m,s,t,t1,t2,t3,ans=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init(n);
    for(int i=1;i<=m;i++)
    {
        e[i].w=inf;//设置初始值用于判断重边
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t1,&t2,&t3);
        e[i].u=t1,e[i].v=t2,e[i].w=t3;
        if(e[i].w>t3)//重边取小的那个
        {
            e[i].u=t1;
            e[i].v=t2;
            e[i].w=t3;
        }
    }
    qsort(e+1,m,sizeof(node),cmp);//排序
    for(int i=1;i<=m;i++)
    {
        if(cb(e[i].u,e[i].v)==1)
        {
            ans=e[i].w;//反复更新ans
        }
        if(find(s)==find(t))break;//如果s和t已经联通就结束
    }
    printf("%d",ans);
}
/*
3 3 1 3
1 2 5
2 3 1
1 3 3
*/

P1195 口袋的天空

题目背景

小杉坐在教室里透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里看起来很漂亮小杉想摘下那样美的几朵云做成棉花糖。

题目描述

给你云朵的个数 NN再给你 M个关系表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 K个棉花糖一个棉花糖最少要用掉一朵云小杉想知道他怎么连花费的代价最小。

输入格式

第一行有三个数 N,M,KN,M,K。

接下来 MM 行每行三个数 X,Y,LX,Y,L表示 XX 云和 YY 云可以通过 LL 的代价连在一起。

输出格式

对每组数据输出一行仅有一个整数表示最小的代价。

如果怎么连都连不出K 个棉花糖请输出 No Answer。

输入输出样例

输入 #1复制

3 1 2

1 2 1

输出 #1复制

1

说明/提示

对于 30\%30% 的数据1 \le N \le 1001≤N≤1001\le M \le 10^31≤M≤103

对于 100\%100% 的数据1 \le N \le 10^31≤N≤1031 \le M \le 10^41≤M≤1041 \le K \le 101≤K≤101 \le X,Y \le N1≤X,Y≤N0 \le L<10^40≤L<104。

思路最小生成树的题要求生成k棵树n个结点n-1条边为一棵树n个结点n-2条边为俩棵树所以n个结点n-k条边为k棵树所以我们的结束条件为cnt==n-k

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
struct node
{
    int u,v,w;
}e[10005];
int f[1005];
int cmp(const void*p1,const void *p2)//回调函数
{
     return ((node *)p1)->w-((node *)p2)->w;
}
void init(int n)//用于父亲数组的初始化
{
    for(int i=0;i<=n;i++)
    {
        f[i]=i;
    }
}
//并查集
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
int cb(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        f[x]=y;
        return 1;
    }
    return 0;
}
int main()
{
    int N,M,K,t1,t2,t3,cnt,ans=0;
    scanf("%d%d%d",&N,&M,&K);
    init(N);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d%d",&t1,&t2,&t3);
        e[i].u=t1,e[i].v=t2,e[i].w=t3;
    }
    qsort(e+1,M,sizeof(node),cmp);//快速排序
    for(int i=1;i<=M;i++)
    {
        if(cb(e[i].u,e[i].v)==1)//不在同一集合
        {
            cnt++;//边的个数
            ans+=e[i].w;//权值累加
        }
        if(cnt==N-K)break;
    }
    if(cnt==N-K)printf("%d",ans);
    else printf("No Answer");//非联通
}