文章目录
题目题目大意分析举个例子原图第一步第二步第三步
代码
题目
Clearing Up
题目大意
给出一个
n
n
n（
1
≤
n
≤
1
0
3
1\leq n\leq 10^3
1≤n≤103）个点
m
m
m（
1
≤
m
≤
1
0
5
1\leq m\leq 10^5
1≤m≤105）条边的图，每条边有个颜色，要么是S，要么是M，要求一个该图的生成树，使得两种颜色的边各占一半。
分析
n
n
n是偶数时无解。
举个例子
原图
原图（红S，黑M）：
第一步
先用Kruskal把S边做一个生成树：
第二步
然后在上面的基础上继续Kruskal插入所有可以插入的M边：
第三步
然后对剩下的M边，用Kruskal进行破圈：
先强制插入该边： 然后对之前的答案图跑Kruskal，得到一条现在不能用的S边（下图中加粗的边）：从之前的答案中删除这条S边，加入这条M边：
于是就成功地把一个S边环成了M边 用这个操作不断替换，直到达成条件。
代码
#include<bits/stdc++.h>
using namespace std
;
int read(){
int x
=0;bool f
=0;char c
=getchar();
while(c
<'0'||c
>'9') f
|=c
=='-',c
=getchar();
while(c
>='0'&&c
<='9') x
=x
*10+(c
^48),c
=getchar();
return f
?-x
:x
;
}
#define MAXN 1000
#define MAXM 100000
#define NO return puts("-1"),0
int N
,M
;
struct Edge
{
int u
,v
,c
;
}E
[MAXM
+5];
struct DSU
{
int fa
[MAXN
+5];
DSU(){}
DSU(int n
){
for(int i
=1;i
<=n
;i
++)
fa
[i
]=i
;
}
int Find(int x
){
return fa
[x
]==x
?x
:fa
[x
]=Find(fa
[x
]);
}
bool Same(int x
,int y
){
return Find(x
)==Find(y
);
}
void Union(int x
,int y
){
fa
[Find(x
)]=Find(y
);
}
};
set
<int> Ans
;
int Kruskal(int id
){
DSU
tmp(N
);
tmp
.Union(E
[id
].u
,E
[id
].v
);
for(int i
:Ans
){
int u
=E
[i
].u
,v
=E
[i
].v
;
if(!tmp
.Same(u
,v
))
tmp
.Union(u
,v
);
else if(E
[i
].c
)
return i
;
}
return -1;
}
void Output(bool sign
){
printf("%d\n",Ans
.size());
for(int i
:Ans
)
if(sign
)
printf("(%d %d %c)\n",E
[i
].u
,E
[i
].v
,E
[i
].c
?'S':'M');
else
printf("%d ",i
);
}
int main(){
N
=read(),M
=read();
for(int i
=1;i
<=M
;i
++){
int u
=read(),v
=read();
char str
[10];scanf("%s",str
);
E
[i
].u
=u
,E
[i
].v
=v
,E
[i
].c
=str
[0]=='S';
}
if((N
-1)&1)
NO
;
DSU
C(N
);
int cnt0
=0,cnt1
=0,Half
=(N
-1)/2;
for(int i
=1;i
<=M
;i
++){
int u
=E
[i
].u
,v
=E
[i
].v
;
if(E
[i
].c
&&!C
.Same(u
,v
)){
cnt1
++;
C
.Union(u
,v
);
Ans
.insert(i
);
}
}
for(int i
=1;i
<=M
;i
++){
if(E
[i
].c
)
continue;
int u
=E
[i
].u
,v
=E
[i
].v
;
if(!C
.Same(u
,v
)){
cnt0
++;
C
.Union(u
,v
);
Ans
.insert(i
);
}
}
for(int i
=1;i
<=M
&&cnt0
<Half
;i
++){
if(E
[i
].c
)
continue;
int u
=E
[i
].u
,v
=E
[i
].v
;
int id
=Kruskal(i
);
if(id
!=-1){
cnt1
--,cnt0
++;
Ans
.erase(id
),
Ans
.insert(i
);
}
}
if(cnt0
==Half
&&cnt1
==Half
)
Output(0);
else
puts("-1");
}
