【poj3683、3678&&hdu1814】2-SAT练习

2015.06.15 16:38 Mon | 21次阅读 | 旧日oi | 固定链接 | 源码

今天学了2SAT,刷了6道题,建图都不太难,选三个作为模板贴一下吧
贴一下1814的题目大意
hdu1814
一国有n个党派,每个党派在议会中都有2个代表,现要组建和平委员会,要从每个党派在议会的代表中选出1人,一共n人组成和平委员会。已知有一些代表之间存在仇恨,也就是说他们不能同时被选为和平委员会的成员,现要你判断满足要求的和平委员会能否创立?如果能,给出字典序最小的方案,否则输出“NIE"。
剩下两道可以去看http://blog.csdn.net/jarjingx/article/details/8521690讲的很好,还有上面提到的论文和PPT一定要看。
hdu1814
要求字典序最小,所以要用O(n*m)的类似模拟的解法,实际上要快很多。感觉跟dancing link挺像,都是从一个位置开始,能判断出好多好多点

我的程序

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 50005
vector<int> son[N];
int n,m,top;
int mark[N],st[N];
void Init()
{
    for(int i=0;i<2*n;i++) son[i].clear();
    memset(mark,0,sizeof(mark));
}
bool dfs(int x)
{
    if(mark[x^1]) return 0;
    if(mark[x]) return 1;
    st[++top]=x;mark[x]=1;
    for(int i=0;i<son[x].size();i++)
    if(!dfs(son[x][i])) return 0;
    return 1;
}
bool work()
{
    for(int i=0;i<2*n;i+=2)
    if(!mark[i]&&!mark[i+1])
    {
        top=0;
        if(!dfs(i))
        {
            while(top) mark[st[top--]]=0;
            if(!dfs(i+1)) return 0; 
        }
    }
    return 1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        Init();
        for(int a,b,i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);a--;b--;
            son[a].push_back(b^1);
            son[b].push_back(a^1);
        }
        if(work())
        {
            for(int i=0;i<n;i++)
            if(mark[2*i]) printf("%d\n",2*i+1);
            else printf("%d\n",2*i+2);
        }
        else puts("NIE");
    }
}
poj3683
读入比较恶心,但是想法很简单,要求输出方案
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 2005
int n,cnt,tot,tim;
int s[N],t[N],d[N];
int dfn[N],low[N],scc[N];
int ord[N],ind[N],opp[N],col[N];
vector<int> son[N];
stack<int> st;
struct edge
{
    int to,next;
}e[N*N];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
bool check(int x,int y)
{
    if(s[x]>=t[y]) return 0;
    if(t[x]<=s[y]) return 0;
    return 1;
}
void dfs(int u)
{
    dfn[u]=low[u]=++tim;st.push(u);
    for(int v,i=h[u];i;i=e[i].next)
    {
        if(!dfn[v=e[i].to])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        cnt++;int x=-1;
        while(x!=u) scc[x=st.top()]=cnt,st.pop();
    }
}
void topsort(int u)
{
    ind[u]=-1;ord[++tot]=u;
    for(int i=0;i<son[u].size();i++)
    {
        ind[son[u][i]]--;
        if(!ind[son[u][i]]) topsort(son[u][i]);
    } 
}
void dfs2(int u)
{
    col[u]=2;
    for(int i=0;i<son[u].size();i++)
    if(!col[son[u][i]]) dfs2(son[u][i]);
}
void print(int x,int y)
{
    int t1=x/60,t2=x%60;
    printf("%02d:%02d ",t1,t2);
    t1=y/60,t2=y%60;
    printf("%02d:%02d\n",t1,t2);
}
int main()
{
    cin>>n;
    for(int a,b,c,d,i=0;i<n;i++) 
    {
        scanf("%1d%1d%*c",&a,&b);
        scanf("%1d%1d",&c,&d);
        s[i*2]=(a*10+b)*60+c*10+d;
        scanf("%1d%1d%*c",&a,&b);
        scanf("%1d%1d",&c,&d);
        t[i*2+1]=(a*10+b)*60+c*10+d;
        scanf("%d",&d);
        t[i*2]=s[i*2]+d;s[i*2+1]=t[i*2+1]-d;
    }
    for(int i=0;i<2*n;i++)
    for(int j=i+1;j<2*n;j++)
    if(check(i,j)&&((i^1)!=j))
    ae(i,j^1),ae(j,i^1);
    for(int i=0;i<2*n;i++) if(!dfn[i]) dfs(i);
    for(int i=0;i<2*n;i++)
    if(scc[i]==scc[i^1])
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int u=0;u<2*n;u++)
    {
        for(int v,i=h[u];i;i=e[i].next)
        if(scc[u]!=scc[v=e[i].to])
        {
            son[scc[v]].push_back(scc[u]);
            ind[scc[u]]++;
        }
        opp[scc[u]]=scc[u^1];
        opp[scc[u^1]]=scc[u];
    }
    for(int i=1;i<=cnt;i++) if(!ind[i]) topsort(i);
    for(int i=1;i<=cnt;i++)
    {
        int k=ord[i];
        if(col[k]) continue;
        col[k]=1;dfs2(opp[k]);
    }
    for(int i=0;i<2*n;i++)
    if(col[scc[i]]==1) print(s[i],t[i]);
    return 0;
}
poj3678
这题建图稍微复杂,涉及到某个点必须选或者必须不选的问题,这在上面的blog里也有讲
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 5005
int n,m,cnt,tim;
int dfn[N],low[N],scc[N];
stack<int> st;
struct edge
{
    int to,next;
}e[N*N];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void dfs(int u)
{
    dfn[u]=low[u]=++tim;st.push(u);
    for(int v,i=h[u];i;i=e[i].next)
    {
        if(!dfn[v=e[i].to])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        cnt++;int x=-1;
        while(x!=u) scc[x=st.top()]=cnt,st.pop();
    }
}
char s[3];
int main()
{
    cin>>n>>m;
    for(int a,b,c,i=0;i<m;i++) 
    {
        scanf("%d%d%d%s",&a,&b,&c,s);
        a*=2;b*=2;
        if(s[0]=='A')
        {
            if(c) ae(a,a^1),ae(b,b^1);
            else ae(a^1,b),ae(b^1,a);
        }
        else if(s[0]=='O')
        {
            if(c) ae(a,b^1),ae(b,a^1);
            else ae(a^1,a),ae(b^1,b);
        }
        else
        {
            if(c) ae(a,b^1),ae(b,a^1),ae(a^1,b),ae(b^1,a);
            else ae(a,b),ae(b^1,a^1),ae(b,a),ae(b^1,a^1);
        }
    }
    for(int i=0;i<2*n;i++) 
    if(!dfn[i]) dfs(i);
    for(int i=0;i<2*n;i++)
    if(scc[i]==scc[i^1])
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    return 0;
}```