danihao123's Blog

图论填坑中……

这题不难，直接造图搞MST（严格讲是最小瓶颈生成树）即可。比较感人的是，Kruskal竟然也能过……

代码：

/**************************************************************
    Problem: 2429
    User: danihao123
    Language: C++
    Result: Accepted
    Time:320 ms
    Memory:12592 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1001,maxm=501;
int n;
struct Edge{
    int u,v,d;
    bool operator < (const Edge& x) const{
        return d<x.d;
    }
};
 
// DJoinst Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    for(register int i=1;i<=n;i++)
        p[i]=i;
    // memset(rank,0,sizeof(rank));
}
 
// Kruskal
int m=0;
Edge E[maxn*maxn];
int MST(){
    register int i,ans,count=0;
    init_set();
    sort(E,E+m);
    for(i=0;i<m && count<=(n-1);i++){
        if(!is_same(E[i].u,E[i].v)){
            union_set(E[i].u,E[i].v);
            ans=E[i].d;
            count++;
        }
    }
    return ans;
}
 
int MK[maxm],Tree[maxn][2];
int main(){
    int monkey;
    register int i,j,sd,ans=0;
    scanf("%d",&monkey);
    for(i=1;i<=monkey;i++)
        scanf("%d",&MK[i]);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&Tree[i][0],&Tree[i][1]);
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            E[m].u=i;
            E[m].v=j;
            E[m].d=hypot(abs(Tree[i][0]-Tree[j][0]),abs(Tree[i][1]-Tree[j][1]));
            m++;
        }
    }
    sd=MST();
    for(i=1;i<=monkey;i++)
        if(MK[i]>=sd)
            ans++;
    printf("%d\n",ans);
    return 0;
}

这道题就是求最小瓶颈生成树中边的最大值。

然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。

代码：

/**************************************************************
    Problem: 1682
    User: danihao123
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:940 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<n;i++)
#define REPB(i,n) for(i=1;i<=n;i++)
#define FROMG_TO E[i].u,E[i].v
const int maxn=2001,maxm=10001;
int n,m;
// Djoint set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    // memset(rank,0,sizeof(rank));
}
// Graph
struct Edge{
    int u,v,d;
};
int cmp(const Edge& a,const Edge& b){
    return a.d<b.d;
}
Edge E[maxm];
int mst(){
    register int i,cnt=0,ans=0;
    init_set();
    sort(E,E+m,cmp);
    for(i=0;cnt<(n-1) && i<m;i++){
        if(!is_same(FROMG_TO)){
            union_set(FROMG_TO);
            ans=max(ans,E[i].d);
            cnt++;
        }
    }
    return ans;
}
int main(){
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
    }
    printf("%d\n",mst());
    return 0;
}