2-sat就是想办法靠到最核心的代码上,而且一般会和二分拆点结合,最核心的思想是HDU 1814 Peaceful Commission,这个题目思想最直接,但是HDU – 3715是结合最好的题目,以这个题目作为板子,字典序输出还没看,留一下吧!

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=1e5+500;
int a[maxn],b[maxn],c[maxn];
int head[maxn];
int n,m,cont;
//tarjan
int vis[maxn];
int low[maxn];
int dfn[maxn];
int color[maxn];
int stk[maxn];
int cnt,index,sig;
struct Edge{
    int u;int v;int next;
}E[maxn];
void add(int u,int v){
    E[cont].u=u;
    E[cont].v=v;
    E[cont].next=head[u];
    head[u]=cont++;
}
void Tarjan(int u){
    vis[u]=1;
    stk[++index]=u;
    low[u]=dfn[u]=cnt++;
    for(int i=head[u];i!=-1;i=E[i].next){
        int v=E[i].v;
        if(vis[v]==0)
            Tarjan(v);
        if(vis[v]==1)
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        sig++;
        do{
            color[stk[index]]=sig;
            vis[stk[index]]=-1;
        }
        while(stk[index--]!=u);
    }
}
int Judge(){
    index=-1;
    sig=0;
    cnt=1;
    memset(stk,0,sizeof(stk));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(color,0,sizeof(color));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n*2;i++){
        if(vis[i]==0){
            Tarjan(i);
        }
    }
    for(int i=0;i<n;i++){
        if(color[i]==color[i+n])
            return 0;
    }
    return 1;
}
int Dichotomize(){
    int l=0,r=m-1;
    int mid;
    while(r-l>=0){
        mid=(l+r)/2;
        cont=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<=mid;i++){
            int dep=i;
            if(c[i]==0){
                add(a[dep],b[dep]+n);
                add(b[dep],a[dep]+n);
            }else if(c[i]==1){
                add(a[dep],b[dep]);
                add(a[dep]+n,b[dep]+n);
                add(b[dep],a[dep]);
                add(b[dep]+n,a[dep]+n);
            }else if(c[i]==2){
                add(a[dep]+n,b[dep]);
                add(b[dep]+n,a[dep]);
            }
        }
        if(Judge()==0){
            r=mid-1;
        }
        if(Judge()==1){
            l=mid+1;
        }
    }
    return l;
}
int main(){
    int T;cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        }
        printf("%d\n",Dichotomize());
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注