题意分析
给定一张图，每一条边都对应着一个 ( 或 )，构造一条路径使得最终形成的括号序列是合法的。
首先，这个序列想要合法，长度肯定得是偶数，且其中 (、) 的数量相等。
那么我们将序列分开来看，已经能够匹配上的 ( 和 ) 先不管，那么匹配不了的只能形如 )...(。（否则就匹配上了）
考虑到合法路径一定是个环（起点、终点相同），因此我们可以通过更换起点的方式来更改序列的顺序，使得最终环上的序列合法。
对于每一条边赋一个权值：( 则为 $1$，) 则为 $-1$，这样我们就可以很好的判断环上路径是否合法，仅仅需要判断环上路径权值之和是否为 $0$ 即可。
因此我们考虑环。
显然，环可以分为正环、负环、零环（和为 $0$），零环显然成立。
而对于正环、负环，明显都可以用来调整 (、) 的数量。
因此我们最开始就可以在不考虑序列合法性的情况下，遍历所有的边，之后利用正环、负环调整数量使其合法。
那么我们判断正环、负环数量即可。
- 同时有正环、负环：
Yes。 - 只有正环：
No。 - 只有负环：
No。 - 没有正环也没有负环：
Yes。（即零环，因为环必然存在）
那么 Bellman-Ford $\mathcal O(nm)$ 求解即可。
对于正环，将权值取反后再跑一遍负环即可。
AC 代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=4000,M=8000;
struct edge{
int u,v,w;
}a[M+1];
int n,m;
bool Bellman_Ford(){
static int dis[N+1];
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=1;i<=n;i++){
bool flag=true;
for(int j=1;j<=m;j++){
if(dis[a[j].u]+a[j].w<dis[a[j].v]){
dis[a[j].v]=dis[a[j].u]+a[j].w;
flag=false;
}
}if(flag)return false;
}return true;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;char ch;
scanf("%d %d",&a[i].u,&a[i].v);
cin>>ch;
a[i].w=(ch=='('?1:-1);
}bool ans=Bellman_Ford();
for(int i=1;i<=m;i++)a[i].w=-a[i].w;
ans^=Bellman_Ford();
printf("%s\n",(ans?"No":"Yes"));
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
