最小生成树

难度1

最好别用prim,用greedy+MFset的生成树算法

是最小生成树吗？

Kruskal？？

二分 & dfs。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> pa;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)

vector<pa> ed[500];
int n, m;
int co[300000];
bool av[300000];
//queue<int> res;
bool df[500];

void dfs(int x){
df[x] = true;
bool tjs = true;
For(i, 1, n){
if (!df[i]){
tjs = false;
break;
}
}
if (tjs){
return;
}
For2(i, ed[x].begin(), ed[x].end()){
if (av[(*i).second] && !df[(*i).first]){
// df[(*i).first] = true;
dfs((*i).first);
}
}
}

bool ok(int x){
For(i, 1, m){
av[i] = true;
}
For(i, 1, m){
if (co[i] > x){
av[i] = false;
}
}
For(i, 1, n){
df[i] = false;
}
dfs(1);
For(i, 1, n){
if (!df[i]){
return false;
}
}
return true;

}

int bi(int x, int y){
if (x == y){ return x;}
int t = ((x + y) / 2);
if (ok(t)){
return bi(x, t);
} else{
return bi(t + 1, y);
}
}

int main(){
For(i, 0, 299999){
av[i] = true;
}
cin >> n >> m;
int tsl, twn, tvi;
For(i, 1, m){
cin >> tsl >> twn >> tvi;
ed[tsl].push_back(make_pair(twn, i));
ed[twn].push_back(make_pair(tsl, i));
co[i] = tvi;
}

// cout << ok(5) << endl;
cout << n - 1 << ' ' << bi(0, 10001) << endl;
return 0;
}

/*
一个标准的最小生成树问题
第一个答案自然就是点数n-1了
第二个答案就应该是加入的最大边权
就是我们加到n-1条边时的最后那条边了~
自然就是最大权值
这样直接一个Kruskal就可以解决问题
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=305;
const int MAXM=MAXN*MAXN;
struct Edge
{
    int x,y,w;
    bool operator<(const Edge& b)const
    {
        return w<b.w;
    }
}e[MAXM];
int fa[MAXN];
int n,m;

inline int find(int& x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    for(int i=1;i<=n;i++)
        fa[i]=i;
}

void Kruskal()
{
    sort(e+1,e+m+1);
    int tot=0,ans;
    for(int i=1;i<=m;i++)
    {
        int& x=e[i].x;  int& y=e[i].y;  int& w=e[i].w;
        int fx=find(x); int fy=find(y);
        if(fx!=fy)
        {
            fa[fx]=fy;
            tot++;
            if(tot==n-1)
            {
                ans=w;
                break;
            }
        }
    }
    printf("%d %d\n",tot,ans);
}

int main()
{
    init();
    Kruskal();
}
     

关键点是,节点的权重最小是1!

这道题和p1234的代码几乎一模一样啊

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,f[510];
int ff(int x){return x==f[x]?x:f[x]=ff(f[x]);}
struct edge{
int l,r,v;
}e[100010];
bool cmp(edge a,edge b){return a.v<b.v;}
int main()
{
scanf("%d%d",&n,&m);
int i,t=0,ans=0;
for(i=1;i<=m;++i)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].v);
sort(e+1,e+m+1,cmp);
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i)
{
if(ff(e[i].l)!=ff(e[i].r))
{
f[ff(e[i].l)]=ff(e[i].r);
ans=e[i].v;t++;
}
}
printf("%d %d",t,ans);
}


#include <cstdio>
#include <cstring>
#include <algorithm>
int f[305];
struct edge
{
    int from,to,len;
}road[10005];
bool comp(edge a,edge b){
    return a.len<b.len;
}
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    int n,m,maxw=0;
    scanf("%d%d",n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].len);
    std::sort(road+1,road+m+1,comp);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1,j=0;i<=m && j<n-1;i++) {
        int p1=getf(road[i].from);
        int p2=getf(road[i].to);
        if(p1!=p2) {
            maxw=road[i].len;
            f[p1]=p2;
        }
    }
    printf("%d %d",n-1,maxw);
    return 0;
}

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;

int i,j,k,n,m,tot,cost;
int f[10001],x[10001],y[10001],z[10001];

struct node{
int s,e,data;
}a[10001];

bool cmp(node x,node y){
return x.data<y.data;
}

int findroot(int u){
int path[10001],k,root;
k=0;root=u;
while (f[root]!=root){
k++;
path[k]=root;
root=f[root];
}
for (i=1;i<=k-1;i++)
f[path[i]]=root;
return root;
}

int main()
{
//freopen("kruskarl.in","r",stdin);
//freopen("kruskarl.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&x[i],&y[i],&z[i]);
a[i].s=x[i];
a[i].e=y[i];
a[i].data=z[i];
}
int Max=0;
sort(a+1,a+m+1,cmp);
for (i=1;i<=n;i++) f[i]=i;
for (int I=1;I<=m;I++){
int r1,r2;
r1=findroot(a[I].s);
r2=findroot(a[I].e);
if (r1!=r2) {
f[r2]=r1;
tot++;
Max=max(Max,a[I].data);
}
if (tot==n-1) break;
}
printf("%d %d",tot,Max);
}
好裸的kruskarl

#include <cstdio>
#include <algorithm>
//#define debug

struct road{
int p1,p2,val;
}map[300*300+50];

int n,m,pre[301];

int find(int x){
int r=x;
while(r!=pre[r])
r=pre[r];

int i=x,j;
while(i!=r){
j=pre[i];
pre[i]=r;
i=j;

}

return r;
}

void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}

bool cmp(road a,road b){
return a.val<b.val;
}

int main(){
#ifdef debug
freopen("in.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
int p1,p2,val;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&p1,&p2,&val);
map[i].p1=p1;
map[i].p2=p2;
map[i].val=val;
}
for(int i=1;i<=n;i++)
pre[i]=i;

std::sort(map+1,map+m+1,cmp);
int count=1;
for(int i=1;i<=m;i++){
p1=map[i].p1;
p2=map[i].p2;
val=map[i].val;
if(find(p1)!=find(p2)){
count++;
join(p1,p2);
}
if(count==n)
break;
}
printf("%d %d",n-1,val);

return 0;
}

http://www.cnblogs.com/JSZX11556/p/4356438.html MST

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
bool dot[100001]; //dot[i]为true时，表示点i没有进生成树，反之……你懂得……
int g[1001][1001]; //邻接矩阵
int minn[10001]; //表示没有进生成树的点离其一个进生成树的点的最近距离
int main(){
memset(minn,0x7f,sizeof(minn));
memset(dot,1,sizeof(dot));
memset(g,0x7f,sizeof(g));
int i,j,k,n,m;
int u,v,c;
int total=0;
int maxn=0;
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>u>>v>>c;
g[u][v]=g[v][u]=c;
}
minn[1]=0; //从第1个点开始
for(i=1;i<=n;i++){
int k=0;
for(j=1;j<=n;j++)
if(dot[j] && minn[j]<minn[k]) k=j; //找出一个没有进生成树的点离一个进生成树的点的最近距离的点
dot[k]=0; //让它进生成树
for(j=1;j<=n;j++)
if(dot[j] && g[k][j]<minn[j]) minn[j]=g[k][j];
}
for(i=1;i<=n;i++){
if(minn[i]>maxn) maxn=minn[i]; //找出分值最大的边
}
cout<<n-1<<" "<<maxn<<endl; //n-1表示n个点用n-1条边连接起来的只可能是树
return 0;
}

/*最小生成树prim算法，注意用vector<int>to[N],cost[N]时起始下标为0和初始化等问题*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=305;
const int maxx=0x7fffffff/4;
vector<int> to[N],cost[N];
int num[N],vis[N],minn[N];
int m,n,tot;
int MAX=0;
/*inline int min(int x,int y){
if(x>y) return y;
else return x;
}*/
int main()
{
for(int i=0;i<=304;i++){
to[i].push_back(maxx);
cost[i].push_back(maxx);
minn[i]=maxx;
}

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
num[a]++; num[b]++;//和a，b相连的点的个数
to[a].push_back(b);
to[b].push_back(a);
cost[a].push_back(c);
cost[b].push_back(c);
}
minn[1]=0;
for(int i=1;i<=n;i++){
int minl=maxx;
int k=0;
for(int j=1;j<=n;j++){
if(vis[j]==0&&minn[j]<minl){
minl=minn[j];
k=j;
}
}
if(k==0) break;
vis[k]=1;
if(minn[k]!=0){
tot++;
MAX=max(MAX,minn[k]);
}
for(int p=1;p<=num[k];p++){
int r=to[k][p];
if(vis[r]==0){
minn[r]=min(minn[r],cost[k][p]);
}
}
}

printf("%d %d",tot,MAX);
return 0;
}

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n , m;

struct line
{
int x , y;
int cost;
};

int cmp( line a , line b )
{
if( a.cost < b.cost )
return 1;
return 0;
}

line link[10000 + 10];
int i;
int pre[10000 + 10];

int find( int x )
{
if( x == pre[x] )
return x;
int t = find( pre[x] );
pre[x] = t;
return t;
}

void merge( int a , int b )
{
pre[ find( a ) ] = find( b );
return;
}

void kruskal()
{
int sum;
int max_cost;
max_cost = 0;
sum = 0;
sort( link , link + m , cmp );
for( i = 0 ; i < m ; i++ )
{
if( find( link[i].x ) != find( link[i].y ) )
{
sum++;
max_cost = link[i].cost;
merge( link[i].x , link[i].y );
}
if( sum == n - 1 )
break;
}
cout << n - 1 << " " << max_cost << endl;
return;
}

void init()
{
int i;
for( i = 1 ; i <= n ; i++ )
pre[i] = i;
return;
}

int main()
{
scanf( "%d %d" , &n , &m );
init();
for( i = 0 ; i < m ; i++ )
scanf( "%d %d %d" , &link[i].x , &link[i].y , &link[i].cost );
kruskal();
return 0;
}

只能说它太水……
最小生成树的思想，水过
var father,u,v,w:array[0..100000] of longint;
ans,i,a,b,c,n,m:longint;

procedure qsort(a,b:longint);
var i,j,x,temp:longint;
begin
i:=a;
j:=b;
x:=w[(i+j) div 2];
repeat
while w[i]<x do inc(i);
while w[j]>x do dec(j);
if i<=j then
begin
temp:=w[i];
w[i]:=w[j];
w[j]:=temp;
temp:=u[i];
u[i]:=u[j];
u[j]:=temp;
temp:=v[i];
v[i]:=v[j];
v[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if i<b then qsort(i,b);
if a<j then qsort(a,j);
end;

function getfather(k:longint):longint;
var tip:longint;
begin
if father[k]=k then exit(k);
tip:=father[k];
father[k]:=getfather(tip);
getfather:=father[k];
end;

procedure kruskal;
var i,t1,t2:longint;
begin
for i:=1 to m do
begin
t1:=getfather(u[i]);
t2:=getfather(v[i]);
if t1<>t2 then
begin
father[t1]:=t2;
ans:=w[i];
end;
end;
end;

begin
//assign(input,'vj.in');
//assign(output,'vj.out');
//reset(input);
//rewrite(output);
readln(n,m);
for i:=1 to m do
begin
readln(a,b,c);
u[i]:=a;
v[i]:=b;
w[i]:=c;
end;
for i:=1 to n do father[i]:=i;
qsort(1,m);
kruskal;
writeln(n-1,' ',ans);
//close(input);
//close(output);
end.