<div class="dp-highlighter bg_cpp"><div class="bar"><div class="tools"><b>[cpp]</b> <a href="#" class="ViewSource" title="view plain" onclick="dp.sh.Toolbar.Command('ViewSource',this);return false;">view plain</a><a href="#" class="CopyToClipboard" title="copy" onclick="dp.sh.Toolbar.Command('CopyToClipboard',this);return false;">copy</a><a href="#" class="PrintSource" title="print" onclick="dp.sh.Toolbar.Command('PrintSource',this);return false;">print</a><a href="#" class="About" title="?" onclick="dp.sh.Toolbar.Command('About',this);return false;">?</a><div style="position: absolute; left: 0px; top: 0px; width: 0px; height: 0px; z-index: 99;"><embed id="ZeroClipboardMovie_2" src="http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf" loop="false" menu="false" quality="best" bgcolor="#ffffff" width="0" height="0" name="ZeroClipboardMovie_2" align="middle" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" flashvars="id=2&width=0&height=0" wmode="transparent"></div></div></div><ol start="1" class="dp-cpp"><li class="alt"><span><span>並查集 </span></span></li><li class=""><span>題意：找出給定的這些話中是否有沖突。若沒有則最多有多少句是對的。 </span></li></ol></div><pre name="code" class="cpp" style="display: none;">並查集
題意：找出給定的這些話中是否有沖突。若沒有則最多有多少句是對的。</pre><br>
<pre></pre>
<div class="dp-highlighter bg_cpp"><div class="bar"><div class="tools"><b>[cpp]</b> <a href="#" class="ViewSource" title="view plain" onclick="dp.sh.Toolbar.Command('ViewSource',this);return false;">view plain</a><a href="#" class="CopyToClipboard" title="copy" onclick="dp.sh.Toolbar.Command('CopyToClipboard',this);return false;">copy</a><a href="#" class="PrintSource" title="print" onclick="dp.sh.Toolbar.Command('PrintSource',this);return false;">print</a><a href="#" class="About" title="?" onclick="dp.sh.Toolbar.Command('About',this);return false;">?</a><div style="position: absolute; left: 0px; top: 0px; width: 0px; height: 0px; z-index: 99;"><embed id="ZeroClipboardMovie_3" src="http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf" loop="false" menu="false" quality="best" bgcolor="#ffffff" width="0" height="0" name="ZeroClipboardMovie_3" align="middle" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" flashvars="id=3&width=0&height=0" wmode="transparent"></div></div></div><ol start="1" class="dp-cpp"><li class="alt"><span><span class="comment">/*</span> </span></li><li class=""><span><span class="comment">思路：如果第x句說y是對的，則x，y必定是一起的，x+n，y+n是一起的；反之x，y+n//y，x+n是一起的。</span> </span></li><li class="alt"><span><span class="comment"> 利用並查集判斷 x 和 x+n 是否在同一集合。</span> </span></li><li class=""><span><span class="comment"> 至於查找最多正確的話，對這些 “小樹” 進行dfs即可。</span> </span></li><li class="alt"><span><span class="comment">*/</span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<stdio.h></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<string.h></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<stdlib.h></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<algorithm></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<iostream></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<queue></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<map></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<stack></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<set></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<math.h></span><span> </span></span></li><li class=""><span><span class="keyword">using</span><span> </span><span class="keyword">namespace</span><span> std; </span></span></li><li class="alt"><span><span class="keyword">typedef</span><span> </span><span class="datatypes">long</span><span> </span><span class="datatypes">long</span><span> int64; </span></span></li><li class=""><span><span class="comment">//typedef __int64 int64;</span><span> </span></span></li><li class="alt"><span><span class="keyword">typedef</span><span> pair<int64,int64> PII; </span></span></li><li class=""><span><span class="preprocessor">#define MP(a,b) make_pair((a),(b)) </span><span> </span></span></li><li class="alt"><span><span class="keyword">const</span><span> </span><span class="datatypes">int</span><span> maxn = 2005; </span></span></li><li class=""><span><span class="keyword">const</span><span> </span><span class="datatypes">int</span><span> inf = 0x7fffffff; </span></span></li><li class="alt"><span><span class="keyword">const</span><span> </span><span class="datatypes">double</span><span> pi=acos(-1.0); </span></span></li><li class=""><span><span class="keyword">const</span><span> </span><span class="datatypes">double</span><span> eps = 1e-8; </span></span></li><li class="alt"><span> </span></li><li class=""><span><span class="datatypes">int</span><span> fa[ maxn ]; </span></span></li><li class="alt"><span><span class="datatypes">int</span><span> rank[ maxn ]; </span></span></li><li class=""><span><span class="keyword">struct</span><span> Edge{ </span></span></li><li class="alt"><span> <span class="datatypes">int</span><span> u,v,next; </span></span></li><li class=""><span>}edge[ maxn<<1 ]; </span></li><li class="alt"><span><span class="datatypes">int</span><span> cnt,head[ maxn ]; </span></span></li><li class=""><span><span class="datatypes">int</span><span> vis[ maxn ]; </span></span></li><li class="alt"><span><span class="datatypes">int</span><span> Cnt_true,Cnt_false; </span></span></li><li class=""><span> </span></li><li class="alt"><span><span class="keyword">void</span><span> init( </span><span class="datatypes">int</span><span> n ){ </span></span></li><li class=""><span> cnt = 0; </span></li><li class="alt"><span> <span class="comment">//Cnt_true = Cnt_false = 0;</span><span> </span></span></li><li class=""><span> memset( head,-1,<span class="keyword">sizeof</span><span>( head ) ) ; </span></span></li><li class="alt"><span> <span class="keyword">for</span><span>( </span><span class="datatypes">int</span><span> i=1;i<=n;i++ ){ </span></span></li><li class=""><span> fa[ i ] = i; </span></li><li class="alt"><span> rank[ i ] = 1; </span></li><li class=""><span> vis[ i ] = 0; </span></li><li class="alt"><span> } </span></li><li class=""><span>} </span></li><li class="alt"><span> </span></li><li class=""><span><span class="keyword">void</span><span> addedge( </span><span class="datatypes">int</span><span> a,</span><span class="datatypes">int</span><span> b ){ </span></span></li><li class="alt"><span> edge[ cnt ].u = a; </span></li><li class=""><span> edge[ cnt ].v = b; </span></li><li class="alt"><span> edge[ cnt ].next = head[ a ]; </span></li><li class=""><span> head[ a ] = cnt ++ ; </span></li><li class="alt"><span> </span></li><li class=""><span> edge[ cnt ].u = b; </span></li><li class="alt"><span> edge[ cnt ].v = a; </span></li><li class=""><span> edge[ cnt ].next = head[ b ]; </span></li><li class="alt"><span> head[ b ] = cnt ++ ; </span></li><li class=""><span>} </span></li><li class="alt"><span> </span></li><li class=""><span><span class="datatypes">int</span><span> find( </span><span class="datatypes">int</span><span> x ){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>( x==fa[x] ) </span></span></li><li class=""><span> <span class="keyword">return</span><span> x; </span></span></li><li class="alt"><span> <span class="keyword">return</span><span> fa[x] = find( fa[x] ); </span></span></li><li class=""><span>} </span></li><li class="alt"><span> </span></li><li class=""><span><span class="keyword">void</span><span> union_ab( </span><span class="datatypes">int</span><span> x,</span><span class="datatypes">int</span><span> y ){ </span></span></li><li class="alt"><span> <span class="datatypes">int</span><span> fax = find( x ); </span></span></li><li class=""><span> <span class="datatypes">int</span><span> fay = find( y ); </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>( rank[ fax ]>rank[ fay ] ){ </span></span></li><li class=""><span> fa[ fay ] = fax; </span></li><li class="alt"><span> rank[ fax ] += rank[ fay ]; </span></li><li class=""><span> } </span></li><li class="alt"><span> <span class="keyword">else</span><span> { </span></span></li><li class=""><span> fa[ fax ] = fay; </span></li><li class="alt"><span> rank[ fay ] += rank[ fax ]; </span></li><li class=""><span> } </span></li><li class="alt"><span>} </span></li><li class=""><span> </span></li><li class="alt"><span><span class="keyword">void</span><span> dfs( </span><span class="datatypes">int</span><span> x,</span><span class="datatypes">int</span><span> n ){ </span></span></li><li class=""><span> vis[ x ] = 1; </span></li><li class="alt"><span> <span class="keyword">if</span><span>( x<=n ){ </span></span></li><li class=""><span> vis[ x+n ] = 1; </span></li><li class="alt"><span> Cnt_true ++ ; </span></li><li class=""><span> <span class="comment">//若x是正確的，則x+n則是錯誤的，同時也不用再去訪問。</span><span> </span></span></li><li class="alt"><span> } </span></li><li class=""><span> <span class="keyword">else</span><span> { </span></span></li><li class="alt"><span> vis[ x-n ] = 1; </span></li><li class=""><span> Cnt_false ++ ; </span></li><li class="alt"><span> } </span></li><li class=""><span> <span class="keyword">for</span><span>( </span><span class="datatypes">int</span><span> i=head[x];i!=-1;i=edge[i].next ){ </span></span></li><li class="alt"><span> <span class="datatypes">int</span><span> y = edge[i].v; </span></span></li><li class=""><span> <span class="keyword">if</span><span>( !vis[y] ){ </span></span></li><li class="alt"><span> dfs( y,n ); </span></li><li class=""><span> } </span></li><li class="alt"><span> } </span></li><li class=""><span>} </span></li><li class="alt"><span> </span></li><li class=""><span><span class="datatypes">int</span><span> main(){ </span></span></li><li class="alt"><span> <span class="datatypes">int</span><span> n; </span></span></li><li class=""><span> <span class="keyword">while</span><span>( scanf(</span><span class="string">"%d"</span><span>,&n)==1,n ){ </span></span></li><li class="alt"><span> init( n*2 ); </span></li><li class=""><span> <span class="datatypes">bool</span><span> f = </span><span class="keyword">true</span><span>; </span></span></li><li class="alt"><span> <span class="datatypes">char</span><span> s1[ 24 ],s2[ 24 ],s3[ 24 ]; </span></span></li><li class=""><span> <span class="datatypes">int</span><span> x1,y1,x2,y2; </span></span></li><li class="alt"><span> <span class="datatypes">int</span><span> fax,fay; </span></span></li><li class=""><span> <span class="keyword">for</span><span>( </span><span class="datatypes">int</span><span> i=1;i<=n;i++ ){ </span></span></li><li class="alt"><span> scanf(<span class="string">"%s%d%s%s"</span><span>,s1,&y1,s2,s3); </span></span></li><li class=""><span> x1 = i,x2 = i+n; </span></li><li class="alt"><span> y1 = y1,y2 = y1+n; </span></li><li class=""><span> <span class="comment">//x1表示true，x2表示false</span><span> </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>( f==</span><span class="keyword">false</span><span> ) </span><span class="keyword">continue</span><span>; </span></span></li><li class=""><span> <span class="keyword">if</span><span>( s3[0]==</span><span class="string">'f'</span><span> ){ </span></span></li><li class="alt"><span> fax = find( x1 ); </span></li><li class=""><span> fay = find( y1 ); </span></li><li class="alt"><span> <span class="keyword">if</span><span>( fax==fay ){ </span></span></li><li class=""><span> f = <span class="keyword">false</span><span>; </span></span></li><li class="alt"><span> <span class="keyword">continue</span><span>; </span></span></li><li class=""><span> } </span></li><li class="alt"><span> fax = find( x2 ); </span></li><li class=""><span> fay = find( y2 ); </span></li><li class="alt"><span> <span class="keyword">if</span><span>( fax==fay ){ </span></span></li><li class=""><span> f = <span class="keyword">false</span><span>; </span></span></li><li class="alt"><span> <span class="keyword">continue</span><span>; </span></span></li><li class=""><span> } </span></li><li class="alt"><span> union_ab( x1,y2 ); </span></li><li class=""><span> union_ab( x2,y1 ); </span></li><li class="alt"><span> addedge( x1,y2 ); </span></li><li class=""><span> addedge( x2,y1 ); </span></li><li class="alt"><span> } </span></li><li class=""><span> <span class="keyword">else</span><span> { </span></span></li><li class="alt"><span> </span></li><li class=""><span> fax = find( x1 ); </span></li><li class="alt"><span> fay = find( y2 ); </span></li><li class=""><span> <span class="keyword">if</span><span>( fax==fay ){ </span></span></li><li class="alt"><span> f = <span class="keyword">false</span><span>; </span></span></li><li class=""><span> <span class="keyword">continue</span><span>; </span></span></li><li class="alt"><span> } </span></li><li class=""><span> fax = find( x2 ); </span></li><li class="alt"><span> fay = find( y1 ); </span></li><li class=""><span> <span class="keyword">if</span><span>( fax==fay ){ </span></span></li><li class="alt"><span> f = <span class="keyword">false</span><span>; </span></span></li><li class=""><span> <span class="keyword">continue</span><span>; </span></span></li><li class="alt"><span> } </span></li><li class=""><span> </span></li><li class="alt"><span> union_ab( x1,y1 ); </span></li><li class=""><span> union_ab( x2,y2 ); </span></li><li class="alt"><span> addedge( x1,y1 ); </span></li><li class=""><span> addedge( x2,y2 ); </span></li><li class="alt"><span> } </span></li><li class=""><span> } </span></li><li class="alt"><span> <span class="keyword">if</span><span>( f==</span><span class="keyword">false</span><span> ) { </span></span></li><li class=""><span> puts(<span class="string">"Inconsistent"</span><span>); </span></span></li><li class="alt"><span> <span class="keyword">continue</span><span>; </span></span></li><li class=""><span> }<span class="comment">//specail judge</span><span> </span></span></li><li class="alt"><span> <span class="keyword">for</span><span>( </span><span class="datatypes">int</span><span> i=1;i<=n;i++ ){ </span></span></li><li class=""><span> <span class="keyword">if</span><span>( find(i)==find(i+n) ){ </span></span></li><li class="alt"><span> f = <span class="keyword">false</span><span>; </span></span></li><li class=""><span> <span class="keyword">break</span><span>; </span></span></li><li class="alt"><span> } </span></li><li class=""><span> } </span></li><li class="alt"><span> <span class="keyword">if</span><span>( f==</span><span class="keyword">false</span><span> ) { </span></span></li><li class=""><span> puts(<span class="string">"Inconsistent"</span><span>); </span></span></li><li class="alt"><span> <span class="keyword">continue</span><span>; </span></span></li><li class=""><span> } </span></li><li class="alt"><span> <span class="datatypes">int</span><span> ans = 0; </span></span></li><li class=""><span> <span class="keyword">for</span><span>( </span><span class="datatypes">int</span><span> i=1;i<=2*n;i++ ){ </span></span></li><li class="alt"><span> <span class="keyword">if</span><span>( !vis[i] ){ </span></span></li><li class=""><span> Cnt_false = Cnt_true = 0; </span></li><li class="alt"><span> dfs( i,n ); </span></li><li class=""><span> ans += max( Cnt_true,Cnt_false ); </span></li><li class="alt"><span> } </span></li><li class=""><span> }<span class="comment">//find the max</span><span> </span></span></li><li class="alt"><span> printf(<span class="string">"%d\n"</span><span>,ans ); </span></span></li><li class=""><span> } </span></li><li class="alt"><span> <span class="keyword">return</span><span> 0; </span></span></li><li class=""><span>} </span></li></ol></div><pre name="code" class="cpp" style="display: none;">/*
思路：如果第x句說y是對的，則x，y必定是一起的，x+n，y+n是一起的；反之x，y+n//y，x+n是一起的。
利用並查集判斷 x 和 x+n 是否在同一集合。
至於查找最多正確的話，對這些 “小樹” 進行dfs即可。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = 2005;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
int fa[ maxn ];
int rank[ maxn ];
struct Edge{
int u,v,next;
}edge[ maxn<<1 ];
int cnt,head[ maxn ];
int vis[ maxn ];
int Cnt_true,Cnt_false;
void init( int n ){
cnt = 0;
//Cnt_true = Cnt_false = 0;
memset( head,-1,sizeof( head ) ) ;
for( int i=1;i<=n;i++ ){
fa[ i ] = i;
rank[ i ] = 1;
vis[ i ] = 0;
}
}
void addedge( int a,int b ){
edge[ cnt ].u = a;
edge[ cnt ].v = b;
edge[ cnt ].next = head[ a ];
head[ a ] = cnt ++ ;
edge[ cnt ].u = b;
edge[ cnt ].v = a;
edge[ cnt ].next = head[ b ];
head[ b ] = cnt ++ ;
}
int find( int x ){
if( x==fa[x] )
return x;
return fa[x] = find( fa[x] );
}
void union_ab( int x,int y ){
int fax = find( x );
int fay = find( y );
if( rank[ fax ]>rank[ fay ] ){
fa[ fay ] = fax;
rank[ fax ] += rank[ fay ];
}
else {
fa[ fax ] = fay;
rank[ fay ] += rank[ fax ];
}
}
void dfs( int x,int n ){
vis[ x ] = 1;
if( x<=n ){
vis[ x+n ] = 1;
Cnt_true ++ ;
//若x是正確的，則x+n則是錯誤的，同時也不用再去訪問。
}
else {
vis[ x-n ] = 1;
Cnt_false ++ ;
}
for( int i=head[x];i!=-1;i=edge[i].next ){
int y = edge[i].v;
if( !vis[y] ){
dfs( y,n );
}
}
}
int main(){
int n;
while( scanf("%d",&n)==1,n ){
init( n*2 );
bool f = true;
char s1[ 24 ],s2[ 24 ],s3[ 24 ];
int x1,y1,x2,y2;
int fax,fay;
for( int i=1;i<=n;i++ ){
scanf("%s%d%s%s",s1,&y1,s2,s3);
x1 = i,x2 = i+n;
y1 = y1,y2 = y1+n;
//x1表示true，x2表示false
if( f==false ) continue;
if( s3[0]=='f' ){
fax = find( x1 );
fay = find( y1 );
if( fax==fay ){
f = false;
continue;
}
fax = find( x2 );
fay = find( y2 );
if( fax==fay ){
f = false;
continue;
}
union_ab( x1,y2 );
union_ab( x2,y1 );
addedge( x1,y2 );
addedge( x2,y1 );
}
else {
fax = find( x1 );
fay = find( y2 );
if( fax==fay ){
f = false;
continue;
}
fax = find( x2 );
fay = find( y1 );
if( fax==fay ){
f = false;
continue;
}
union_ab( x1,y1 );
union_ab( x2,y2 );
addedge( x1,y1 );
addedge( x2,y2 );
}
}
if( f==false ) {
puts("Inconsistent");
continue;
}//specail judge
for( int i=1;i<=n;i++ ){
if( find(i)==find(i+n) ){
f = false;
break;
}
}
if( f==false ) {
puts("Inconsistent");
continue;
}
int ans = 0;
for( int i=1;i<=2*n;i++ ){
if( !vis[i] ){
Cnt_false = Cnt_true = 0;
dfs( i,n );
ans += max( Cnt_true,Cnt_false );
}
}//find the max
printf("%d\n",ans );
}
return 0;
} </pre><br>
