CF605B的题解
算是对 Leap_Frog大佬的补充吧qwq。
%%% Leap_Frog.
我们来看一下大佬的这段话：
考虑倒着思考 Kruskal 算法。
按边权从小到大排序。
每次插入一条边。
如果是树边，那就新开节点。
否则在当前节点内任意连边。
这样构造，每次非树边插入都比当前两端小。
所以必然正确。
对于“如果是树边，那就新开节点。”这句话，可以理解成我们构造一个以 \(1\) 号点为中心的菊花图（所有点都连向 \(1\) 号点）。对于第 \(i\) 条树边，建一条从 \(1\) 连向 \(i+1\) 的边。
就是这样子：
对于“否则在当前节点内任意连边。”这句话，我们插入非树边的时候为了不能重复（题目有要求两点之间不能有多条边），设我们目前已经处理了 \(i\) 条树边（即目前我们已经开了 \(i+1\) 个点），现在要插的边是从 \(u\) 连向 \(v\)，那么我们 \(u\) 可以从 \(j\) 开始 \((3\le j\le i+1)\)，\(v\) 从 \(2\) 开始建边。每建完一条边，\(v\) 就加 \(1\)，如果 \(u=v\)，那么 \(u\) 加 \(1\)，\(v\) 回退到 \(2\) 重新开始为下一次的建边做准备。
\(-1\) 的情况就是我们目前开的点不够用（即 \(u=i+1,v=i\))。
放几张图理解一下吧qwq：
这样子代码是不是好理解一点啦qwq.
没有压行的代码（Leap_Frog大佬压行的代码感觉不太好读TaT）：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
struct edge
{
int u;
int v;
int w;
int id;
int yes;
}e[100010];
int tot=1;//目前已开的点的数量，我们要设为1，因为我们得先开好1号节点
bool cmp1(edge a,edge b)
{
if(a.w==b.w) return a.yes>b.yes;
return a.w<b.w;
}
bool cmp2(edge a,edge b)
{
return a.id<b.id;
}
int u=2,v=3;//记得初始化
bool flag=1;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].w,&e[i].yes);
e[i].id=i;
}
sort(e+1,e+1+m,cmp1);
for(int i=1;i<=m;i++)
{
if(e[i].yes) e[i].u=1,e[i].v=++tot;//如果是树边
else//如果是非树边
{
if(v>tot)//无解
{
flag=0;
break;
}
e[i].u=u++;
e[i].v=v;
if(u==v) v++,u=2;
}
}
if(!flag) printf("-1");
else
{
sort(e+1,e+1+m,cmp2);//最后要记得按一开始的输入顺序排序
for(int i=1;i<=m;i++) printf("%d %d\n",e[i].u,e[i].v);
}
return 0;
}
完结撒花~