【2-sat】8.14B. 黑心老板

2-sat 只写过板子

题目大意

有一个长度为$k$取值只有01的序列，现在$n$个人每人下注三个位置，请构造一个序列使每个人最多猜对一个位置

$kle 5000,n le 10000$

题目分析

挂博客纯粹只是为了警示自己

这个题只是肤浅地以为是个3-sat，以至于想了好久的网络流建图。

只能说这两个东西都没深刻掌握吧，不然也不至于这个样子

 1 #include<bits/stdc++.h>
 2 const int maxn = 15035;
 3 const int maxm = 80035;
 4 
 5 int n,m,stk[maxn],top;
 6 int edgeTot,head[maxn],edges[maxm],nxt[maxm];
 7 bool vis[maxn],chk;
 8 
 9 int get()
10 {
11     int x = 0;
12     scanf("%d",&x);
13     char c = getchar();
14     while (c!='R'&&c!='B') c = getchar();
15     return x*2-(c=='B')-1;
16 }
17 void addedge(int u, int v)
18 {
19     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
20 }
21 bool dfs(int x)
22 {
23     if (vis[x^1]) return false;
24     if (vis[x]) return true;
25     vis[x] = true, stk[++top] = x;
26     for (int i=head[x]; i!=-1; i=nxt[i])
27         if (!dfs(edges[i])) return false;
28     return true;
29 }
30 bool load(int x)
31 {
32     top = 0;
33     bool val = dfs(x);
34     if (!val) for (int i=1; i<=top; i++) vis[stk[i]] = false;
35     return val;
36 }
37 int main()
38 {
39     memset(head, -1, sizeof head);
40     scanf("%d%d",&n,&m);
41     for (int i=1,a,b,c; i<=m; i++)
42     {
43         a = get(), b = get(), c = get();
44         addedge(a, b^1), addedge(a, c^1);
45         addedge(b, a^1), addedge(b, c^1);
46         addedge(c, a^1), addedge(c, b^1);
47     }
48     chk = true;
49     for (int i=0; i<2*n&&chk; i+=2)
50         if (!vis[i]&&!vis[i^1]){
51             if (!load(i)){
52                 if (!load(i^1)) chk = false;
53             }
54         }
55     if (!chk) puts("-1");
56     else for (int i=0; i<2*n; i+=2)
57         putchar(vis[i]?'B':'R');
58     return 0;
59 }

END