。。。八中OJ上居然没有题目。。
不过我还是找到了题目。。
tdt.sjtu.edu.cn/~rma/USACO/task/2006/Open/twohead.txt
这个下午没什么心情。。就去八中OJ刷USACO的水题。。
水了很多道囧。发现这道算最有意思的瀑布汗。。
首先可以发现显然可以贪心的分配。。
就是每次都到一个个往当前的段加，知道不满足为止。。
判断是否满足就是个简单的2-SAT。。
我考虑了两个想法。。
要么是每次暴力2-SAT。。显然TLE。。
如果二分的话。。那么也是可能会TLE的。。
所以只好搞动态维护。。
先说一下构图。。
1A表示Cow1的头A。。
那么如果1A 讨厌 2A。
那么1A <-> 2B 1B<->2A..
连线表示一定要在一边。。
如果什么时候发现1A<->1B。。
就矛盾了。。
我表示传统的并查集面对这样的询问只能悲剧。。
所以只好使用非常规的。。就是启发式合并的那个。。
而且为了询问是否有这种。。需要用set。。。
然后就差不多了。。
恩。。这个复杂度有点惊悚。。
启发式合并本身就是NLogN的，加上还要用set。。
就是NLogN^2的。。。
不过居然AC了。。
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(set<int>::iterator e=x.begin();e!=x.end();e++)
#define trV(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
struct UF
{
set<int> node[maxn];
int root[maxn];
UF()
{
rep(i,maxn)
root[i]=i,node[i].insert(i);
}
bool Union(int i,int j)
{
i=root[i];j=root[j];
if(i!=j)
{
if(node[i].size()<node[j].size())
swap(i,j);
tr(e,node[j])
{
int x=*e;
if(node[i].find(x^1)!=node[i].end())return false;
node[i].insert(x);root[x]=i;
}
node[j].clear();
}
return true;
}
}U;
int n,m;
vector<int> E[maxn];
void AddEdge(int s,int t)
{
if(s<t)swap(s,t);
E[s].pb(t);
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int s;char c;
rep(i,m)
{
cin>>s>>c;–s;int a=s*2+c-‘A’;
cin>>s>>c;–s;int b=s*2+c-‘A’;
AddEdge(a,b^1);AddEdge(b,a^1);
}
int ans=0;int pre=-1;
rep(i,n)
{
for(int t=i*2;t<i*2+2;t++)
trV(e,E[t])if(*e>pre*2+1&&!U.Union(t,*e))
{
ans++;
pre=i;
continue;
}
}
ans++;
cout<<ans<<endl;
}