hdu3715 2-sat+二分

时间:2024-12-15 09:33:49

Go Deeper

题意:确定一个0/1数组(size:n)使得满足最多的条件数。条件在数组a,b,c给出。

吐槽:哎,一水提,还搞了很久!关键是抽象出题目模型(如上的一句话)。以后做二sat:有哪些是点,哪些是条件,分清!,然后注意细节。这次居然因为里面一个小错误:

判断有无解的时候,i与i+1是否在一个SCC中的时候,i居然没有每次+2!而是++!傻X了。。。囧!还一直以为自己二分写错。。。

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxv=402;//maxe=500000;
int dfn[maxv];int low[maxv];int vis[maxv];int scc[maxv];int ins[maxv];stack<int>sta;
int times=0; int numb=0;
vector<vector<int> >e(maxv);
void tarjan(int u)
{
dfn[u]=low[u]=times++;
ins[u]=1;
sta.push(u);
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(!vis[v])
{
vis[v]=1;
tarjan(v);
if(low[v]<low[u])low[u]=low[v];
}
else if(ins[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(low[u]==dfn[u])
{
numb++;
int cur;
do{
cur=sta.top();
sta.pop();
ins[cur]=0;
scc[cur]=numb;
}while(cur!=u);
}
}
int n,m;int a[10005],b[10005],c[10005];
void init()
{
numb=times=0;
for(int i=0;i<maxv;i++)
{
scc[i]=ins[i]=dfn[i]=low[i]=vis[i]=0;
e[i].clear();
}
}
bool build_solve(int x)
{
init();
for(int i=0;i<=x;i++)
{
if(c[i]==2)
{
e[2*a[i]+1].push_back(2*b[i]);
e[2*b[i]+1].push_back(2*a[i]);
}
else if(c[i]==1)
{
e[2*a[i]].push_back(2*b[i]);
e[2*b[i]].push_back(2*a[i]);
e[2*a[i]+1].push_back(2*b[i]+1);
e[2*b[i]+1].push_back(2*a[i]+1);
}
else if(c[i]==0)
{
e[2*a[i]].push_back(2*b[i]+1);
e[2*b[i]].push_back(2*a[i]+1);
}
}
for(int i=0;i<=2*n-1;i++)
{
if(!vis[i])
{
vis[i]=1;
tarjan(i);
}
}
for(int i=0;i<=2*n-2;i+=2) //开始写成i++!!!!WA到跪!
if(scc[i]==scc[i+1])
return 0;
return 1;
}
void readin()
{
for(int i=0;i<m;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
readin();
int l=0,r=m,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(build_solve(mid))
l=mid;
else
r=mid;
}
printf("%d\n",l+1);
}
return 0;
}