社区讨论
救命,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 条回复,欢迎继续交流。
正在加载回复...