问题标题: 酷町堂：5075 请指出思路错误

0
0
已解决
赵逸凡
赵逸凡
初级启示者
初级启示者 
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int s,n,fa[510],m,cnt;
struct point{
    double x,y;
    bool del;
}dot[510];
struct edge{
    int u,v;
    double w;
    bool flag;
}a[25000];
int size;
double dis(int st,int ed)
{
    return sqrt((dot[st].x-dot[ed].x)*(dot[st].x-dot[ed].x)+(dot[st].y-dot[ed].y)*(dot[st].y-dot[ed].y));
}
void init()
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    fa[x]=y;
}
bool same(int x,int y)
{
    if(find(x)==find(y))
        return true;
    return false;
} 
bool cmp(edge l,edge r)
{
    return l.w<r.w;
}
bool cmp2(edge l,edge r)
{
    if(l.flag!=r.flag)
        return l.flag>r.flag;
    return l.w>r.w;
}
int Kruskal()
{
    double MST=0;
    init();
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(!same(a[i].u,a[i].v))
        {
            unite(a[i].u,a[i].v);
            a[i].flag=true;
            MST+=a[i].w;
        }
    }
    return MST;
}
int main()
{
    cin>>s>>n;
    for(int i=1;i<=n;i++)
        cin>>dot[i].x>>dot[i].y;
    m=n*(n-1)/2;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            a[++size]=(edge){i,j,dis(i,j)}; 
    double mst=Kruskal();
    sort(a+1,a+m+1,cmp2);
    for(int i=1;i<n;i++)
    {
        edge e=a[i];
        if(cnt==s)
            break;
        if(!dot[e.u].del&&!dot[e.v].del)
        {
            dot[e.u].del=true;
            dot[e.v].del=true;
            mst-=e.w;
            cnt++;
        }
        if(!dot[e.u].del&&dot[e.v].del)
        {
            dot[e.u].del=true;
            mst-=e.w;
            cnt++;
        }   
        if(dot[e.u].del&&!dot[e.v].del)
        {
            dot[e.v].del=true;
            mst-=e.w;
            cnt++;
        }
    }
    printf("%.2f",mst);
    return 0;
}

我的思路是用Kruskal求出MST后，再开始贪心：每次在n-1条边(边数是MST的一条定理)中取出边权最大的边，将其两端点置为s座城市的两个结点，然后一直取边、标记点，直到点数到达s时停止，但样例输出的是199.87，求助哪里错了？（老师没回）

举报

10酷町豆 刷题求解 3条评论 4 年，2 月 前

0
已采纳
陈喆鹏
陈喆鹏
资深光能
资深光能

怎么贪心，先Kruskar再深搜应该能那点分

阅读更多
举报

4 年，2 月 前 1条评论

0
赵逸凡
赵逸凡
初级启示者
初级启示者

我一开始以为是我的贪心策略可能出现当取k个边时，恰好总共标记的还剩一个点就能有s个点，我的程序此时会依旧选择边权最大的，而理论上应该取有一个点已被标记过的最大权的边

阅读更多
举报

4 年，2 月 前 0条评论

0
赵逸凡
赵逸凡
初级启示者
初级启示者 
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int s,n,fa[510],m,cnt;
struct point{
    double x,y;
    bool del;
}dot[510];
struct edge{
    int u,v;
    double w;
    bool flag;
}a[25000];
int size;
double dis(int st,int ed)
{
    return sqrt((dot[st].x-dot[ed].x)*(dot[st].x-dot[ed].x)+(dot[st].y-dot[ed].y)*(dot[st].y-dot[ed].y));
}
void init()
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    fa[x]=y;
}
bool same(int x,int y)
{
    if(find(x)==find(y))
        return true;
    return false;
} 
bool cmp(edge l,edge r)
{
    return l.w<r.w;
}
bool cmp2(edge l,edge r)
{
    if(l.flag!=r.flag)
        return l.flag>r.flag;
    return l.w>r.w;
}
int Kruskal()
{
    double MST=0;
    init();
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(!same(a[i].u,a[i].v))
        {
            unite(a[i].u,a[i].v);
            a[i].flag=true;
            MST+=a[i].w;
        }
    }
    return MST;
}
int main()
{
    cin>>s>>n;
    for(int i=1;i<=n;i++)
        cin>>dot[i].x>>dot[i].y;
    m=n*(n-1)/2;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            a[++size]=(edge){i,j,dis(i,j)}; 
    double mst=Kruskal();
    sort(a+1,a+m+1,cmp2);
    for(int i=1;i<n;i++)
    {
        edge e=a[i];
        if(cnt==s)
            break;
        if(!dot[e.u].del&&!dot[e.v].del)
        {
            dot[e.u].del=true;
            dot[e.v].del=true;
            if(cnt+2<=s)
            {
                mst-=e.w;
                cnt+=2;
            }       
        }
        if(cnt==s)
            break;
        if(!dot[e.u].del&&dot[e.v].del)
        {
            dot[e.u].del=true;
            mst-=e.w;
            cnt++;
        }   
        if(cnt==s)
            break;
        if(dot[e.u].del&&!dot[e.v].del)
        {
            dot[e.v].del=true;
            mst-=e.w;
            cnt++;
        }
        if(cnt==s)
            break;
    }
    printf("%.2f",mst);
    return 0;
}

对于两个端点均没标记过的最小生成树的最大权边进行了最后情况（即cnt=s-1）的优化，然而输出的数大于样例，我在cnt==s的情况多次进行了判断，然而还是没用处。正解貌似是筛出n-s条边，但O(n!/s!/(n-s)!)的复杂度我懒得写了。

阅读更多
举报

4 年，2 月 前 1条评论

0
赵逸凡
赵逸凡
初级启示者
初级启示者

@沈峻宇 将n-s条边进行组合，还要用到dfs的性质来枚举各种可能性，我还是听老师讲吧

赵逸凡在2020-09-26 14:22:48追加了内容

update：

样例过了，但是WA

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int s,n,fa[25000],m,cnt;
struct point{
	double x,y;
	bool del;
}dot[25000];
struct edge{
	int u,v;
	double w;
	bool flag;
}a[100000];
int size;
double dis(int st,int ed)
{
	return sqrt((dot[st].x-dot[ed].x)*(dot[st].x-dot[ed].x)+(dot[st].y-dot[ed].y)*(dot[st].y-dot[ed].y));
}
void init()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
}
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)
		return ;
	fa[x]=y;
}
bool same(int x,int y)
{
	if(find(x)==find(y))
		return true;
	return false;
} 
bool cmp(edge l,edge r)
{
	return l.w<r.w;
}
bool cmp2(edge l,edge r)
{
	if(l.flag!=r.flag)
		return l.flag>r.flag;
	return l.w>r.w;
}
int Kruskal()
{
	double MST=0;
	init();
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(!same(a[i].u,a[i].v))
		{
			unite(a[i].u,a[i].v);
			a[i].flag=true;
			MST+=a[i].w;
		}
	}
	return MST;
}
int main()
{
	cin>>s>>n;
	for(int i=1;i<=n;i++)
		cin>>dot[i].x>>dot[i].y;
	m=n*(n-1)/2;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			a[++size]=(edge){i,j,dis(i,j)}; 
	double mst=Kruskal();
	double maxi=-100;
	sort(a+1,a+m+1,cmp2);
	for(int i=1;i<n;i++)
	{
		edge e=a[i];
		if(cnt==s)
			break;
		if(!dot[e.u].del&&!dot[e.v].del)
		{
			dot[e.u].del=true;
			dot[e.v].del=true;
			if(cnt+2<=s)
			{
				mst-=e.w;
				cnt+=2;
			}		
		}
		if(cnt==s)
			break;
		if(!dot[e.u].del&&dot[e.v].del)
		{
			dot[e.u].del=true;
			mst-=e.w;
			cnt++;
		}	
		if(cnt==s)
			break;
		if(dot[e.u].del&&!dot[e.v].del)
		{
			dot[e.v].del=true;
			mst-=e.w;
			cnt++;
		}
		if(cnt==s)
			break;
	}
	for(int i=1;i<n;i++)
	{
		edge e=a[i];
		if(!dot[e.v].del||!dot[e.u].del)
			maxi=max(maxi,e.w);
	}
	printf("%.2f",maxi);
	return 0;
}

我标记了最大权值边，但还是错了，请问为什么

 

@黄子扬

阅读更多
举报

4 年，2 月 前 1条评论

0
0
我要回答
© 2021 酷町堂教育机构 版权所有 皖ICP备16015773号-1