社区讨论

救命,unexpected end of file什么鬼

P2323[HNOI2006] 公路修建问题参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6xln1j
此快照首次捕获于
2025/11/20 12:28
4 个月前
此快照最后确认于
2025/11/20 12:28
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1e4+10;

int n,k,m,ans;
int fa[maxn],rec[maxn];
struct line
{
	int x,y,c1,c2,id;
}edge[maxn*2];

int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool cmp1(const line &a,const line &b)
{
	return a.c1<b.c1;
}
bool cmp2(const line &a,const line &b)
{
	return a.c2<b.c2;
}
int main()
{
	scanf("%d %d %d",&n,&k,&m);
	for(int i=1;i<m;i++)scanf("%d %d %d %d",&edge[i].x,&edge[i].y,&edge[i].c1,&edge[i].c2),edge[i].id=i;
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(edge+1,edge+1+m,cmp1);
	int cnt=0;
	for(int i=1;i<m;i++)
	{
		int x=find(edge[i].x),y=find(edge[i].y);
		if(x!=y)
		{
			fa[x]=y;
			cnt++;
			rec[edge[i].id]=1;
		}
		if(cnt==k)
		{
			ans=edge[i].c1;
			break;
		}
	}
	sort(edge+1,edge+1+m,cmp2);
	for(int i=1;i<m;i++)
	{
		int x=find(edge[i].x),y=find(edge[i].y);
		if(x!=y)
		{
			fa[x]=y;
			cnt++;
			rec[edge[i].id]=2;		
		}
		if(cnt==n-1)
		{
			ans=max(ans,edge[i].c2);
			break;
		}
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)if(rec[i])printf("%d %d\n",i,rec[i]);
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...