C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 2671 平衡环

Problem

给定一棵𝑛个点的树,每条边有一个边权,边权只可能是4或7。你想在树上选择两个没有直接连边的点,并在这两点间加一条边权为4或7的连边。很显然,树上出现一个环,如果这个环上边权为4的边数与边权为7的边数相等,那么这个环是一个平衡环。你希望得到这样一个平衡环,请问需要连接哪两个点,并赋予什么边权。

如果有多种方案,输出任意一组解即可。如果无解,输出-1。

数据范围:1≤𝑛≤100

Solution

必定是长度为3的路,一开始dfs点1留影子找,后来发现只能dfs所有点,这样就是𝑂(n^2)的了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<set>
#include<iostream>
#include<stack>
#include<cstring>
#include<vector>
#include<algorithm>

typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

inline int rd() {
int x = 0, f = 1;
char ch;
while (ch < '0' || ch > '9') {
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}

int n,g[1020];
struct E{
int u,v,w,nex;
}e[1020];
int ansu=0,ansv=0;
int f[1020];
void dfs(int d1,int d2,int d3,int l1,int l2){
if(ansu&&ansv) return;
int n4=0,n7=0;
if(l1==4) n4++;
else if(l1==7) n7++;
if(l2==4) n4++;
else if(l2==7) n7++;
for(int i=g[d3];i>0;i=e[i].nex){
if(f[e[i].v]) continue;
if(e[i].w==4) n4++;
else if(e[i].w==7) n7++;
if(n4&&n7&&n4+n7==3){
ansu=1,ansv=1;
if(n4==2){

cout<<d1<<' '<<e[i].v<<' '<<"7"<<endl;
}
else{
cout<<d1<<' '<<e[i].v<<' '<<"4"<<endl;
}
return;
}
if(e[i].w==4) n4--;
else if(e[i].w==7) n7--;
f[e[i].v]=1;
dfs(d2,d3,e[i].v,l2,e[i].w);
f[e[i].v]=0;
}
}
int main(){
io_opt;
cin>>n;
int x,y,z;
for(int i=1;i<=n-1;i++){
cin>>x>>y>>z;
e[i]=(E){x,y,z,g[x]};g[x]=i;
e[i+n-1]=(E){y,x,z,g[y]};g[y]=i+n-1;
}

for(int i=1;i<=n;i++){
ansu=ansv=0;
f[i]=1;
dfs(0,0,i,0,0);
f[i]=0;
if((ansu&&ansv)){
return 0;
}
}
cout<<"-1"<<endl;
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/1548/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!