LightOJ-1251 Forming the Council题解(Tarjan+SCC)

Description

传送门:LightOJ-1251

In a city there are n voters, and m people formed the Govt. council. The council members are numbered from 1 to m. Now everyone is complaining that the council is biased. So, they made a plan. The plan is that the voters are given a chance to vote again to form the new council. A vote will be like ±i ±j. '+' means the voter wants that member to be in the council, '-' means the voter doesn't want the member to be in the council. For example, there are 4 voters, they voted like
+1 -3 the voter wants member 1 to be kept in the council or member 3 to be thrown out
+2 +3 the voter wants member 2 to be kept in the council or member 3 to be kept in the council
-1 -2 the voter wants member 1 to be thrown out or member 2 to be thrown out
-4 +1 the voter wants member 4 to be thrown out or member 1 to be kept in the council
A voter will be satisfied if at least one of his wishes becomes true. Now your task is to form the council such that all the voters are happy.


Input

Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 20000) and m (1 ≤ m ≤ 8000). Each of the next n lines contains a vote in the form ±i ±j (1 ≤ i, j ≤ m).

Output

For each case, print the case number and 'Yes' if a solution exists, or 'No' if there is no solution. Then if the result is yes, print another line containing the number of members in the council followed by the members in ascending order. And print a single space between two numbers. There can be many solutions. Any valid one will do.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
4 3
+1 +3
+2 -1
+2 -3
-1 -2
4 2
+1 -2
+1 +2
-1 -2
-1 +2
1 3
+1 -3

Sample Output

1
2
3
4
5
Case 1: Yes
2 2 3
Case 2: No
Case 3: Yes
0

题目大意

题目的意思就是有n个民众和m个候选人,每个民众有两个愿望,希望某个候选人是议会成员或者不是议会成员,如果这个民众的两个愿望至少有一个实现,那么这个民众就算被满足,现在问是否有满足所有民众的情况,有的话输出可行解。

思路

对于这种问题,我们很容易可以想到2-SAT,对于这个题,我们采用Tarjan+SCC来求解。
对于每个民众有+a或-a,+a代表该民众希望a号候选人是议会成员,-a代表该民众不希望a号议员是议会成员。
对于每一个候选人i,我们规定编号i为i被选上,i+n为落选,那么我们有四种情况,对于每种情况我们连相应的边。
+a +b:(b+n) -> a,(a+n) -> b
+a -b:b -> a,(a+n) -> (b+n)
-a +b:(b+n) -> (a+n),a -> b
-a -b:b -> (a+n),a -> (b+n)
建完边之后我们求联通分量然后缩点,对于缩点之后得到的DAG,我们反向建图,然后拓扑排序得到可行解。

代码

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/************************************************************
> File Name: Forming_the_Council2.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Wed 02 Oct 2019 10:19:31 PM CST
************************************************************/

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc o<<1
#define rc o<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 40005;
const int MAXM = 70005;
const int MOD = 1e9+7;
const double PI = acos(-1.0);
const double EXP = 1e-8;
struct Edge{
int to,next;
}edge1[MAXM],edge2[MAXM];
int out[MAXN];
int vis[MAXM];
int Low[MAXM];
int DFN[MAXM];
int print[MAXN];
int Stack[MAXM];
int color[MAXM];
int pos[MAXM];
int deg[MAXM];
int head1[MAXM],tot1;
int head2[MAXM],tot2;
int n, m, scc, cnt, cont, top;
void init(){
tot1 = tot2 = 0;
memset(head1,0,sizeof head1);
memset(head2,0,sizeof head2);
}
void add_edge1(int u,int v){
edge1[++tot1].to = v;
edge1[tot1].next = head1[u];
head1[u] = tot1;
}
void add_edge2(int u,int v){
edge2[++tot2].to = v;
edge2[tot2].next = head2[u];
head2[u] = tot2;
}
void Top(){
memset(print,0,sizeof print);
queue<int>s;
for(int i = 1;i <= scc;i++)
if(deg[i]==0)
s.push(i);
while(!s.empty()){
int u = s.front();
s.pop();
if(print[u]==0){
print[u] = 1;
print[pos[u]] = 2;
}
for(int i = head2[u];i;i = edge2[i].next){
int v = edge2[i].to;
deg[v]--;
if(deg[v]==0)
s.push(v);
}
}
cont = 0;
for(int i = 1;i <= n;i++)
if(print[color[i]]==1)
out[cont++] = i;
}
//求连通分量
void Tarjan(int u){
vis[u] = 1;
DFN[u] = Low[u] = cnt++;
Stack[++top] = u;
for(int i = head1[u];i;i = edge1[i].next){
int v = edge1[i].to;
if(!DFN[v]){
Tarjan(v);
Low[u] = Low[u]>Low[v]?Low[v]:Low[u];
}else if(vis[v]==1 && Low[u] > DFN[v])
Low[u] = DFN[v];
}
if(Low[u]==DFN[u]){
scc++;
do{
vis[Stack[top]] = -1;
color[Stack[top]] = scc;
}while(Stack[top--]!=u);
}
}
//缩点并反拓扑排序
bool solve(){
scc = 0;
cnt = 1;
top = -1;
memset(deg,0,sizeof deg);
memset(Stack,0,sizeof Stack);
memset(DFN,0,sizeof DFN);
memset(Low,0,sizeof Low);
memset(vis,0,sizeof vis);
memset(color,0,sizeof color);
for(int i = 1;i <= n*2;i++)
if(!DFN[i])
Tarjan(i);
for(int i = 1;i <= n;i++){
if(color[i]==color[i+n])
return false;
pos[color[i]] = color[i+n];
pos[color[i+n]] = color[i];
}
for(int u = 1;u <= 2*n;u++)
for(int i = head1[u];i;i = edge1[i].next){
int v = edge1[i].to;
if(color[u]!=color[v]){
deg[color[u]]++;
add_edge2(color[v],color[u]);
}
}
Top();
return true;
}
int main(void){
int t;
scanf("%d",&t);
for(int cas = 1;cas <= t;cas++){
scanf("%d%d",&m,&n);
init();
for(int i = 0;i < m;i++){
int x, y;
scanf("%d%d",&x,&y);
int xx = x,yy = y;
if(x < 0) x = -x;
if(y < 0) y = -y;
if(xx>0&&yy>0) add_edge1(x+n,y),add_edge1(y+n,x);
if(xx>0&&yy<0) add_edge1(x+n,y+n),add_edge1(y,x);
if(xx<0&&yy>0) add_edge1(x,y),add_edge1(y+n,x+n);
if(xx<0&&yy<0) add_edge1(x,y+n),add_edge1(y,x+n);
}
printf("Case %d: ",cas);
if(solve()){
printf("Yes\n");
printf("%d",cont);
for(int i = 0;i < cont;i++)
printf(" %d",out[i]);
printf("\n");
}else
printf("No\n");
}
return 0;
}

本文标题:LightOJ-1251 Forming the Council题解(Tarjan+SCC)

文章作者:TSwifite

发布时间:2019年10月09日 - 22:10

最后更新:2019年10月09日 - 23:10

原始链接:http://tswiftie.com/LightOJ-1251-Forming-the-Council题解-Tarjan-SCC/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%