两个BUG鸣翠柳，一行代码上西天。。。
hdu4786 Fibonacci Tree（生成树）问能否用白边和黑边构成一棵生成树，并且白边数量是斐波那契数。
题解：分别优先加入白边和黑边，求出生成树能包含白边的最大值和最小值，其间有值为斐波那契数即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+;
const int N=1e5+;
struct edge{
int u,v,w;
}e[M];
int f[N];
int fi[];
int n,m,ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i) f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
int u,v,i,cnt=,mi=,ma=,flag=;
init();
for(i=;i<m;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
if(e[i].w) mi++;
if(++cnt==n-){flag=;break;}
}
}
if(!flag){printf("No\n");return;}
init();
for(i=m-;i>=;--i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
if(e[i].w) ma++;
if(++cnt==n-)break;
}
}
for(i=;i<;++i)
if(mi<=fi[i]&&fi[i]<=ma){
printf("Yes\n");return;
}
printf("No\n");
}
int main(){
int t,i,a,b,c,k=;
fi[]=;fi[]=;
for(i=;i<;++i)
fi[i]=fi[i-]+fi[i-];
//printf(".%d.",fi[19]);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(i=;i<m;++i){
scanf("%d%d%d",&a,&b,&c);
e[i]={a,b,c};
}
sort(e,e+m,cmp);
printf("Case #%d: ",k++);
Kruskal();
}
return ;
}
hdu5253 连接的管道（最小生成树）一开始我因为没建好图纠结了ToT~
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
struct edge{
int u,v,w;
}e[N*N*];
int f[N*N];
int g[N][N];
int ei,n,m,ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
int u,v,i,cnt=;
for(ans=i=;i<ei;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
if(++cnt==n*m-)break;
}
}
}
int main(){
int t,i,j,h,k=;
scanf("%d",&t);
while(t--){
ei=;
scanf("%d%d",&n,&m);
for(i=;i<n;++i){
for(j=;j<m;++j){
scanf("%d",&g[i][j]);
f[i*m+j]=i*m+j;
if(i>){
e[ei].u=i*m+j; e[ei].v=(i-)*m+j;
e[ei++].w=abs(g[i][j]-g[i-][j]);
}
if(j>){
e[ei].u=i*m+j; e[ei].v=i*m+j-;
e[ei++].w=abs(g[i][j]-g[i][j-]);
}
}
}
sort(e,e+ei,cmp);
Kruskal();
printf("Case #%d:\n%d\n",k++,ans);
}
return ;
}
hdu1598 find the most comfortable road（最小生成树，枚举）第一眼看过去差点想最短路[吓]，，这是最小差不是最短路哦。用Kruskal要对边排序，贪心正好哩。枚举最小道路建树，起点和终点连上了就记录最大边与最小边之差，最后选所有情况的最小值就行啦。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const int M=;
struct edge{
int u,v,w;
}e[M];
int f[];
int n,m,ans,st,ed;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
int u,v,i,j;
ans=inf;
for(i=;i<m;++i){//枚举
init();
for(j=i;j<m&&e[j].w-e[i].w<ans;++j){
u=e[j].u;
v=e[j].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
}
if(fin(st)==fin(ed)){
ans=min(ans,e[j].w-e[i].w);
break;
}
}
}
}
int main(){
int i,j,q;
while(scanf("%d%d",&n,&m)==){
for(i=;i<m;++i)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e,e+m,cmp);
scanf("%d",&q);
while(q--){
scanf("%d%d",&st,&ed);
Kruskal();
printf("%d\n",(ans==inf)?-:ans);
}
}
return ;
}
poj3522 Slim Span（最小生成树，枚举）求最大边与最小边之差最小的生成树。和上面那题挺像的，相比之下，这题就是完整的最小生成树了。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
struct edge{
int u,v,w;
}e[];
int f[N];
int n,m,ans,st,ed;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
int u,v,i,j,cnt;
ans=inf;
for(i=;i<m;++i){
init(); cnt=;
for(j=i;j<m&&e[j].w-e[i].w<ans;++j){
u=e[j].u;
v=e[j].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
if(++cnt==n-){
ans=min(ans,e[j].w-e[i].w);
break;
}
}
}
}
}
int main(){
int i,j,q;
while(scanf("%d%d",&n,&m),n||m){
for(i=;i<m;++i)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e,e+m,cmp);
Kruskal();
printf("%d\n",(ans==inf)?-:ans);
}
return ;
}
poj2784 Buy or Build（最小生成树，二进制枚举）英语渣在艰难地读题orz。已知n个城市的坐标，q个连通块各自的费用，新建一条边的费用为两点距离的平方。求最小生成树。学了一下二进制枚举法。
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
struct edge{
int u,v,w;
}e[];
struct node{
int x,y;
}V[N];
int f[N];
int a[];
int n,m,q;
vector<int>g[];
int cmp(edge a,edge b){
return a.w<b.w;
}
int dist(int i,int j){
return (V[i].x-V[j].x)*(V[i].x-V[j].x)+(V[i].y-V[j].y)*(V[i].y-V[j].y);
}
void init(){
for(int i=;i<=n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void uni(int x,int y){
if((x=fin(x))==(y=fin(y)))return;
f[x]=y;
}
int Kruskal(){
int u,v,i,j,cnt=,ans=;
for(i=;i<m;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
if(++cnt==n-)break;
}
}
//printf("%d..\n",ans);
return ans;
}
void solve(){
int i,j,k,cost,ans;
init();
ans=Kruskal();
for(i=;i<(<<q);++i){//枚举方案
cost=;
init();
for(j=;j<q;++j){
if(!((i>>j)&))continue;//二进制枚举
cost+=a[j];
//printf("COST:%d..",cost);
for(k=;k<g[j].size();++k)
uni(g[j][k],g[j][]);
}
ans=min(ans,cost+Kruskal());
}
printf("%d\n",ans);
}
int main(){
int i,j,num,x;
while(scanf("%d%d",&n,&q)==){
for(i=;i<q;++i){
g[i].clear();
scanf("%d%d",&num,&a[i]);
for(j=;j<num;++j){
scanf("%d",&x);
g[i].push_back(x);
}
}
for(i=;i<=n;++i) scanf("%d%d",&V[i].x,&V[i].y);
m=;
for(i=;i<n;++i){
for(j=i+;j<=n;++j){
e[m].u=i; e[m].v=j;
e[m++].w=dist(i,j);
}
}
sort(e,e+m,cmp);
solve();
}
return ;
}