题解 - Vijos

2

Lifi LV 10 @ 2019-08-19 22:38:57

1.生成最小生成树，并记录生成树的所以边。输出第一个答案。
2.逐个在边集中剔除最小生成树的某个边，并重新生成除去该边后的最小生成树，直至所有边都去除过一次为止。有n-1条边，剔除n-1次，共得到n-1棵最小生成树。
3.取n-1棵树中的最小值为此小生成树。

#include <iostream>
#include <algorithm>
#include <vector>
#define ULL unsigned long long

using namespace std;

typedef struct
{
    int a,b;
    ULL d;
}edge;

edge g[250000];
int n,m;
int fa[501];
vector<int> vi;
int check;

bool comp(edge a,edge b)
{
    return a.d<b.d;
}

int fi(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    else
    {
        return fa[x]=fi(fa[x]);
    }
}

int MST(bool &nop)
{
    int i,j,a,b,d,aa,bb;
    ULL ans=0;
    for(i=0;i<=n;i++)
    {
        fa[i]=i;
    }
    for(i=0,j=0;i<n-1;i++)
    {
        for(;j<m;j++)
        {
            if(j==check)
            {
                continue;
            }
            a=g[j].a;
            b=g[j].b;
            d=g[j].d;
            aa=fi(a);
            bb=fi(b);
            if(aa!=bb)
            {
                ans+=d;
                fa[bb]=aa;
                if(check==m)
                {
                    vi.push_back(j);
                }
                break;
            }
        }
    }
    if(j==m)
    {
        nop=true;
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    int i;
    ULL ans=0,hax;
    for(i=0;i<m;i++)
    {
        cin>>g[i].a>>g[i].b>>g[i].d;
    }
    sort(g,g+m,comp);
    check=m;
    bool nop;
    nop=false;
    ans=MST(nop);
    if(nop)
    {
        cout<<"Cost: "<<-1<<endl;
        cout<<"Cost: "<<-1<<endl;
        return 0;
    }
    else
    {
        cout<<"Cost: "<<ans<<endl;
    }
    ans=1e18;
    for(i=vi.size()-1;i>=0;i--)
    {
        check=vi[i];
        nop=false;
        hax=MST(nop);
        if(!nop)
        {
            ans=min(ans,hax);
        }
    }
    if(ans<1e18)
    {
        cout<<"Cost: "<<ans<<endl;
    }
    else
    {
        cout<<"Cost: "<<-1<<endl;
    }
    return 0;
}

2

PowderHan LV 10 @ 2017-05-07 22:27:51

/*
经典题啊~次小生成树问题~
在lrj的训练指南上也有啦~
代码写得好丑啊第一次写23333
我们先用Kruskal跑一遍最小生成树
然后这样的话我们根据这个加的边建立起一棵真正的树
并且转换为有根树
这样我们对于树上任意两点我们都可以求出它们唯一路径上的最长边
即f[u][v]表示u到v路径上的最大边权
这里可以直接O(n^2)dfs也可以直接上树上倍增(nlogn)
这样子的话我们就可以直接枚举未加入最小生成树中的边
然后尝试加入~
MST有的边交换性质(次小一定是最小交换一条边来的)
那么对于新加入的边(u,v,w)
我们尝试将此边加入MST中
那么必然是换掉加入后u,v这个环上的除了这条边的最大权值最好
就是我们的f[u][v]
那么这样我们就可以直接O(m)枚举
所以复杂度就是预处理的O(n^2)
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=505;
const int MAXM=250002;
const int INF=(1<<30)-1;
struct Edge1
{
    int from,to,w;
    bool operator <(const Edge1& b)const
    {
        return w<b.w;
    }
}e1[MAXM];
struct Edge
{
    int from,to,w,next;
}e[MAXN<<1];
int fisrt[MAXN];//Edges
int pa[MAXN];//bingcha~
int f[MAXN][MAXN];
int fa[MAXN];//Tree
bool vis[MAXN];
bool have[MAXM];
int n,m,tot;
int ans1,ans2;

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

inline void Add_Edge(int& x,int& y,int& w)
{
    e[++tot].from=x;    e[tot].to=y;
    e[tot].w=w;     e[tot].next=fisrt[x];   fisrt[x]=tot;
}

void init()
{
    memset(fisrt,-1,sizeof(fisrt));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e1[i].from,&e1[i].to,&e1[i].w);
    for(int i=1;i<=n;i++)
        pa[i]=i;
}

void Kruskal()
{
    sort(e1+1,e1+m+1);
    int c=0;
    for(int i=1;i<=m;i++)
    {
        int& x=e1[i].from;  int& y=e1[i].to;    int& w=e1[i].w;
        int fx=find(x); int fy=find(y);
        if(fx!=fy)
        {
            pa[fx]=fy;  have[i]=1;
            Add_Edge(x,y,w);    Add_Edge(y,x,w);
            c++;    ans1+=w;
        }   
        if(c>=n-1)
            break;  
    }
    if(c!=n-1)
        printf("Cost: -1\n");
    else
        printf("Cost: %d\n",ans1);
}

void dfsroot(int u,int father)
{
    fa[u]=father;
    for(int i=fisrt[u];i!=-1;i=e[i].next)
    {
        int& v=e[i].to; int& w=e[i].w;
        if(!fa[v]&&v!=father)
        {
            f[u][v]=f[v][u]=w;
            dfsroot(v,u);
        }
    }
}

void dfs(int u)
{
    int& v=fa[u];
    for(int i=1;i<=n;i++)
        if(vis[i])
            f[i][u]=f[u][i]=max(f[i][v],f[u][v]);
    vis[u]=1;
    for(int i=fisrt[u];i!=-1;i=e[i].next)
        if(fa[e[i].to]==u)
            dfs(e[i].to);
}

void NextKruskal()
{
    ans2=INF;
    for(int i=1;i<=m;i++)
        if(!have[i])
        {
            ans2=min(ans2,ans1-f[e1[i].from][e1[i].to]+e1[i].w);
        }
    if(ans2==INF)
        printf("Cost: -1\n");
    else
        printf("Cost: %d\n",ans2);
}

int main()
{
    init();
    Kruskal();
    dfsroot(1,-1);
    dfs(1);
    NextKruskal();
}

0

Goodhao LV 10 @ 2018-07-29 11:59:26

PowderHan的代码是有BUG的。数据太弱没显示出来。
按照他的代码，会出现某一个点不连通而次小生成树不为-1.
比如下列数据
7 8
2 3 40
3 5 81
7 4 78
1 5 42
4 3 99
3 7 98
4 1 56
1 3 27

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n,m;
vector<pair<int,int> > g[505];
struct edge {
    int x,y,w;
} e[500*500+1];
bool use[500*500+1];
int fa[505];
int dep[505];
int FA[505][16];
int cost[505][16];
int bin[16];
int cnt;
int find(int x) {
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
bool cmp(edge a,edge b) {
    return a.w<b.w;
}
void dfs(int x,int fa,int w) {
    FA[x][0]=fa;
    if (fa) cost[x][0]=w;
    dep[x]=dep[fa]+1;
    FOR(i,15) {
        FA[x][i]=FA[FA[x][i-1]][i-1];
        if (FA[x][i]) cost[x][i]=max(cost[FA[x][i-1]][i-1],cost[x][i-1]);
    }
    for (int i=0;i<g[x].size();i++) {
        int y=g[x][i].first,w=g[x][i].second;
        if (y!=fa) dfs(y,x,w);
    }
}
int dp(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    int d=dep[x]-dep[y];
    int res=0;
    for (int i=0;i<=15;i++) {
        if (d&(bin[i])) {
            res=max(res,cost[x][i]);
            x=FA[x][i];
        }
    }
    for (int i=15;i>=0;i--) {
        if (FA[x][i]!=FA[y][i]) {
            res=max(res,max(cost[y][i],cost[x][i]));
            x=FA[x][i],y=FA[y][i];
        }
    }
    if (x!=y) res=max(res,max(cost[x][0],cost[y][0]));
    return res;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,m) {
        cin>>e[i].x>>e[i].y>>e[i].w;
    }
    sort(e+1,e+1+m,cmp);
    FOR(i,n) fa[i]=i;
    int v1=0,v2=inf;
    FOR(i,m) {
        int u=find(e[i].x),v=find(e[i].y);
        if (u!=v) {
            v1+=e[i].w;
            g[e[i].x].pb(mp(e[i].y,e[i].w));
            g[e[i].y].pb(mp(e[i].x,e[i].w));
            fa[u]=v;
            use[i]=1;
            ++cnt;
        }
    }
    if (cnt<n-1) {
        cout<<"Cost: "<<-1<<endl;
        cout<<"Cost: "<<-1<<endl;
        return 0;
    } else if (cnt==m) {
        cout<<"Cost: "<<v1<<endl;
        cout<<"Cost: "<<-1<<endl;
        return 0;
    }
    bin[0]=1;
    FOR(i,15) bin[i]=bin[i-1]*2;
    dfs(1,0,0);
    int pos=0;
    FOR(i,m) if (!use[i]) {
        int x=e[i].x,y=e[i].y,w=e[i].w;
        int t=dp(x,y);
        if (v1-t+w<v2) {
            pos=i;
            v2=v1-t+w;
        }
    }
    //cout<<pos<<endl;
    //cout<<dp(e[pos].x,e[pos].y)<<endl;
    //1cout<<e[pos].x<<" "<<e[pos].y<<endl;
    cout<<"Cost: "<<v1<<endl;
    cout<<"Cost: "<<v2<<endl;
    return 0;
}

0

130705009 LV 10 @ 2016-01-06 09:02:59

http://accepted.com.cn/vijos1070/

0

Dumpling_李 LV 9 @ 2013-03-06 20:57:44

为什么kruskal求出来的次小生成树比最小生成树还小代码如下
#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
struct self{int x,y;long long c;};
self s[250001];
int a,b,m,n;
long long z=0;
int f[250001];
int use[250001];
bool firstuse[250001]={0};

int find(int i)
{
return f[i]==i?i:f[i]=find(f[i]);
}

int cmp(self a1,self a2)
{
return a1.c<a2.c;
}
long long kruskal1()
{
long long z=0;
int y=0;
for(int k=1;k<=n;k++)
{
int l=find(s[k].x);
int r=find(s[k].y);
if(l!=r)
{
firstuse[k]=1;
f[l]=r;
z+=s[k].c;
y++;
if(y==m-1)return z;

}
}

return z;
}
long long kruskal()
{
long long z=0;
int y=0;
for(int k=1;k<=n;k++)
if(use[k])
{
int l=find(s[k].x);
int r=find(s[k].y);
if(l!=r)
{
f[l]=r;
z+=s[k].c;
y++;
if(y==m-1)return z;
}

}

return z;
}

int main()
{
ios::sync_with_stdio(false);
//freopen("1.in","r",stdin);

cin>>m>>n;
for(a=1;a<=n;a++)
{
f[a]=a;
cin>>s[a].x>>s[a].y>>s[a].c;
use[a]=1;
}
sort(s+1,s+n+1,cmp);

if(n<m-1)
{
cout<<"Cost: "<<-1<<endl;
cout<<"Cost: "<<-1<<endl;
return 0;
}

z=kruskal1();
cout<<"Cost: "<<z<<endl;

if(n-1<m-1)
{
cout<<"Cost: "<<-1<<endl;
return 0;
}

long long T=999999999999;
for(a=1;a<=n;a++)
if(firstuse[a]==1)
{
for(b=1;b<=n;b++)f[b]=b;
use[a]=false;
long long k=kruskal();
if(k<T&&k>=z)T=k;
use[a]=true;
}

cout<<"Cost: "<<T<<endl;
return 0;
}

另外最后几组如何优化我是纯暴力删边枚举的不知道那些0ms 10ms的怎么过的
求并查集删边枚举的代码谢了！

function2 @ 2015-08-11 15:27:32

刚刚拿你的对拍来着……你判断无解的情况貌似写错了

0

SEX丶Elope LV 6 @ 2013-02-16 10:19:15

点击查看程序源码+详细题解

0

sideman LV 8 @ 2010-03-28 21:23:21

kao！ iostream超时！

cstdio ac！

没天理我的ac率啊

0

chengrui LV 10 @ 2009-11-09 14:41:46

没秒杀......囧~~~~

0

song19931218 LV 9 @ 2009-11-08 11:45:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

O(N^2)的prim算法，不过写丑了，没能秒杀

0

傻子同学 LV 10 @ 2009-10-31 18:50:38

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

因为MST是基于贪心的算法因此要枚举

枚举去掉的边再找一条可以替代的就可以了

程序不长 70行+

0

laz LV 10 @ 2009-09-20 12:52:03

汗死、、我就奇怪 O(N*M) 怎么能AC=。= 原来是O(M)的。。无数次的TLE之后

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：59ms

0

zhanghanyuan LV 10 @ 2009-08-11 08:28:02

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

吐血

0

H2SO4HCLHNO3 LV 10 @ 2009-08-10 20:05:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：81ms

先求MST，再穷举，删去MST中的每一条边，求出最小值，就是次小MST

0

罡罡 LV 8 @ 2009-08-04 18:02:44

.......一道题卡了我一下午......忍不住要贴个代码

program vijos1070(input,output);

var

a,f:array[1..501,1..501] of longint;

used:array[1..501] of boolean;

v,s,i,j,k,n,m,m1,min,mini,x,y,z:longint;

dis,father:array[1..501] of longint;

sum:longint;

st,fi:array[1..501] of longint;

b:array[0..501,0..501] of boolean;

function max(a,b:longint):longint;

begin

if a>b then max:=a else max:=b;

end;

{---|---|---|-main---|---|---|---|-}

begin

fillchar(b,sizeof(b),false);

read(n,m);

fillchar(f,sizeof(f),0);

fillchar(used,sizeof(used),false);

for i:=1 to n do

for j:=1 to n do

a:=maxlongint;

for i:=1 to m do

begin

read(x,y,z);

a[x,y]:=z;

a[y,x]:=z;

end;

for i:=1 to n do

dis[i]:=maxlongint;

dis[1]:=0;

s:=1;

x:=1;

sum:=0;

used:=true;

for i:=1 to n do

if amaxlongint then begin

dis[i]:=a;father[i]:=s;end

else father[i]:=-1;

dis:=0;

father:=-1;

while x

0

普及组加强版 LV 9 @ 2009-07-20 11:32:38

n^3 的 prim 为什么超时 7个点？

桐子跟我走吧 @ 2013-10-28 20:41:32

因为后七个点都是n=500

0

NOI金牌神牛 LV 7 @ 2009-06-23 09:07:42

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：387ms

好慢！

0

xyechang LV 10 @ 2009-05-15 16:22:04

我的算法，(N^2)的，速度超快，可惜只过了8个点：

var

g:array[0..500,0..500]of extended;

a,b:array[1..500]of integer;

vd:array[1..500]of boolean;

n,m,i,j,k,t:longint;

c1,c2,l:extended;

begin

readln(n,m);

for i:=0 to n do

for j:=0 to n do

g:=1e30;

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

for i:=1 to m do

begin

readln(j,k,g[j,k]);

g[k,j]:=g[j,k];

if j=1 then

a[k]:=1;

if k=1 then

a[j]:=1;

end;

fillchar(vd,sizeof(vd),false);

vd[1]:=true;

c1:=0;

c2:=1e30;

for t:=2 to n do

begin

k:=0;

l:=1e30;

for i:=1 to n do

if(not vd[i])and(g

0

LV 0 @ 2009-04-06 16:25:29

我用prim竟然超时。。。

0

唐钰小宝 LV 10 @ 2009-04-05 00:19:16

Accepted 有效得分：100 有效耗时：325ms

kruskal+删边

天啊！最大值一定要赋到2147483647!!

血的教训，提交了n多次！！

0

voyagec2 LV 10 @ 2009-03-18 16:07:11

次小生成树

删边后再做一个最小生成树

题解

100 条题解

新年趣事之游戏

信息

状态

开发

支持

题解

100 条题解

新年趣事之游戏

信息

状态

开发

支持

还没有账户？

登录