Go Deeper
Time Limit: 2 Seconds Memory Limit: 65536 KB
Here is a procedure's pseudocode:
go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end
In this code n is an integer. a, b, c and x are 4 arrays of integers. The index of array always starts from 0. Array a and b consist of non-negative integers smaller than n. Array x consists of only 0 and 1. Array c consists of only 0, 1 and 2. The lengths of array a, b and c are m while the length of array x is n.
Given the elements of array a, b, and c, when we call the procedure go(0, n , m) what is the maximal possible value does the procedure output?
Input
There are multiple test cases. The first line of input is an integer T (0 < T ≤ 100), indicating the number of test cases. Then T test cases follow. Each case starts with a line of 2 integers n and m (0 < n ≤ 200, 0 < m ≤ 10000). Then m lines of 3 integers follow. The i-th(1 ≤ i ≤ m) line of them are ai-1 ,bi-1 and ci-1 (0 ≤ ai-1, bi-1 < n, 0 ≤ ci-1 ≤ 2).
Output
For each test case, output the result in a single line.
Sample Input
3
2 1
0 1 0
2 1
0 0 0
2 2
0 1 0
1 1 2
Sample Output
1
1
2
解法:
看到x为二进制数组就很敏感了,然后又看到c的值只能取0,1,2。很快想到了2-sat
t1=a[i],t2=b[i]
如果x[t1]+x[t2]!=0,那么就是说t1的0和t2的0冲突,添加t10->t21和t20->t11
如果x[t1]+x[t2]!=2,那么就是说t1的1和t2的1冲突,添加t11->t20和t21->t10
如果x[t1]+x[t2]!=1,那么就是说t1的0和t2的1冲突,以及t1的1和t2的0冲突,添加t10->t20和t21->t11 以及t11->t21和t20->t10
贴代码
1
# include <cstdio>
2
# include <vector>
3
# include <cstring>
4
using namespace std;
5
int n,m;
6
vector<int> g[500];
7
int a[10005],b[10005],c[10005];
8
int low[500],dfn,color[500],stack[500],top,co;
9
void tarjan(int pos)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
11
int now=dfn++;
12
low[pos]=now;
13
stack[++top]=pos;
14
for(int i=0;i<g[pos].size();i++)
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
16
if(low[g[pos][i]]==-1) tarjan(g[pos][i]);
17
if(low[g[pos][i]]<low[pos]) low[pos]=low[g[pos][i]];
18
}
19
if(low[pos]>=now)
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
21
do
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
23
color[stack[top]]=co;
24
low[stack[top]]=2*n;
25
}while(stack[top--]!=pos);
26
co++;
27
}
28
29
}
30
bool chk(int num)
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
for(int i=0;i<(n<<1);i++)
33
g[i].clear();
34
for(int i=0;i<=num;i++)
35
switch(c[i])
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
37
case 0:
38
g[a[i]*2].push_back(b[i]*2+1);
39
g[b[i]*2].push_back(a[i]*2+1);
40
break;
41
case 1:
42
g[a[i]*2].push_back(b[i]*2);
43
g[b[i]*2+1].push_back(a[i]*2+1);
44
g[a[i]*2+1].push_back(b[i]*2+1);
45
g[b[i]*2].push_back(a[i]*2);
46
break;
47
case 2:
48
g[a[i]*2+1].push_back(b[i]*2);
49
g[b[i]*2+1].push_back(a[i]*2);
50
break;
51
};
52
memset(low,-1,sizeof(low));
53
dfn=co=0;
54
memset(color,-1,sizeof(color));
55
for(int i=0;i<2*n;i++)
56
if(low[i]==-1)
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
58
top=-1;
59
tarjan(i);
60
}
61
for(int i=0;i<n;i++)
62
if(color[2*i]==color[2*i+1])
63
return false;
64
return true;
65
}
66
int main()
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
68
int test;
69
scanf("%d",&test);
70
while(test--)
71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
72
scanf("%d%d",&n,&m);
73
for(int i=0;i<m;i++)
74
scanf("%d%d%d",a+i,b+i,c+i);
75
int s=0,e=m-1;
76
while(s<=e)
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
int mid=(s+e)>>1;
79
if(chk(mid)) s=mid+1;
80
else e=mid-1;
81
}
82
printf("%d\n",s);
83
}
84
return 0;
85
}
86![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
87![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)