现在有一个由 NNN 个点组成的 MMM 条边的简单无向图。一开始所有的边都是白色的。点编号为 1,2,3,…,N1,2,3,\dots,N1,2,3,…,N,第 iii 条边连接点 AiA_iAi, BiB_iBi,并且将这条边染为黑色的代价为 CiC_iCi。你现在需要染色至少四条边,使得:
1、除了某条染为黑色的边以外,剩下所有黑色的边构成一个简单环
2、不在该简单环上的黑色的边连接了一个该简单环上的点和一个不在任何环上的点。
请判断能否染色成功,如果能,输出最小代价,如果不能,则输出 -1。
-1
使用您的 gxyz 通用账户