【题解】小机关城
题面：
天明最近对机关城起了兴趣。 他用一些小物件搭起了一座机关城，当然，这只能算是玩具。 现在，他有n个机关，从1到n编号，他现在想让一些机关联通。 由于一些特殊原因，只有m对机关才可能建立联系。 他打算用绳子连接两个机关表示这两个机关能相互联系。 而连接一对机关所需要的绳子长度可能不同。 他笨手笨脚，所以为了防止绳子打结， 他希望使用的绳子中最长的绳子长度最短。 不过，他又有t个计划，对于每个计划，都有一个参数x， 表示这个计划至少需要x个机关相连。 你要告诉他满足计划条件的最长绳子的最短长度。
分析：
给定n个点m条边，一开始边是断开的，对于一个x，需要连接一些边，使得这个图中存在至少包含x个节点的联通块，求使用的边中，最长的那条边最短是多少。
首先，我们不知道那些边可以选，没有明确的目标
那我们就设选用的最长边不超过k
看看这个k，是否满足“图中存在至少包含x个节点的联通块”
当k恰好满足条件（即k-1无法满足条件），k就是答案“最长的那条边的最短值”
k的取值[1,1024]，一一枚举耗时太长
可以思考
最长的边越长，就越容易满足“图中存在至少包含x个节点的联通块”，具有单调性，可以二分
还需要解决：对于一个k，判断其是否满足条件
最大的联通块包含的点>=x即满足条件
要找到最大的联通块，很明显用dfs
其他细节看注释
总结一下：二分+dfs
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node {
int to,v,nt;
} e[20005];
int n,m,t,p,head[10005],ie,num[10005];
int l,r,mid;
void add(int a,int b,int c) {//邻接表存图
e[++ie].to=b,e[ie].v=c,e[ie].nt=head[a],head[a]=ie;
return ;
}
int dfs(int x) {
//num[x]表示x能到达的且没有走过的点数
//第一次搜一个联通块里的点x，搜完后num[x]就是联通块的点数
if(num[x]!=0) return 0;//num[x]=0表示没搜过，没搜过就搜，否则直接返回
num[x]=1;//自己
for(int i=head[x];i;i=e[i].nt)
if(e[i].v<=mid)//mid即分析里的k，如果该边可选就搜
num[x]+=dfs(e[i].to);//统计该点能到达的且没有走过的点
return num[x];
}
int work(int v) {
for(int i=1;i<=n;i++)//搜联通块
if(dfs(i)>=v)
return 1;//满足
return 0;
}
int main() {
scanf("%d %d %d",&n,&m,&t);
for(int i=1,a,b,c;i<=m;i++) {
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=t;i++) {
scanf("%d",&p);
l=1,r=1025;
while(l<r) {//二分
memset(num,0,4*(n+1));
mid=l+r>>1;
if(work(p)) r=mid;
else l=mid+1;
}
if(l==1025) printf("QAQ\n");//无解
else printf("%d\n",l);
}
return 0;
}