uva 12745 Wishmaster(2-sat)

12745 Wishmaster

view code#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 200010;
const int M = N<<1;
int _, cas=1, n, m, pre[N], S[N], c;
bool mark[N];

struct edge
{
    int u, v, next;
    edge() {}
    edge(int u, int v, int next):u(u),v(v),next(next) {}
}e[M];
int ecnt = 0;

void addedge(int u, int v)
{
    if(u<0) u = -u+n;
    if(v<0) v = -v+n;
    e[ecnt] = edge(u, v, pre[u]);
    pre[u] = ecnt++;
}

bool dfs(int x)
{
    int ano = x>n?x-n:x+n;
    if(mark[ano]) return false;
    if(mark[x]) return true;
    mark[x] = true;
    S[c++] = x;
    for(int i=pre[x]; ~i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfs(v)) return false;
    }
    return 1;
}

bool check()
{
    for(int i=1; i<=n; i++)
    {
        if(!mark[i] && !mark[i+n])
        {
            c = 0;
            if(!dfs(i)){
                while(c>0) mark[S[--c]] = 0;
                if(!dfs(i+n)) return 0;
            }
        }
    }
    return 1;
}

void solve()
{
    scanf("%d%d", &n, &m);
    int u, v;
    ecnt = 0;
    memset(pre, -1, sizeof(pre));
    for(int i=0; i<m; i++)
    {
        scanf("%d%d", &u, &v);
        addedge(-u, v);
        addedge(-v, u);
    }

    memset(mark, 0, sizeof(mark));
    printf("Case %d: ", cas++);
    if(check()) puts("Yes");
    else puts("No");
}

int main()
{
//    freopen("in.txt", "r", stdin);
    cin>>_;
    while(_--) solve();
    return 0;
}
时间: 08-20

uva 12745 Wishmaster(2-sat)的相关文章

UVA 11488 Hyper Prefix Sets (Trie)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2483 Hyper Prefix Sets Prefix goodness of a set string islength of longest common prefix*number of strings in the set.For example the prefix goodnes

uva 1564 - Widget Factory(高斯消元+逆元)

题目链接:uva 1564 - Widget Factory 题目大意:n种零件,m次工作日程,零件序号从1到n,给出m次工作日程的信息,x,s,e,表示生产了x个零件,从星期s开始到星期e(有可能是多个星期),然后给出生产的x个零件的序号.求每个零件被生产需要多少天(保证在3到10天) 解题思路:因为不能确定每个工作日程具体生产了几天,所以对应列出的方程均为线性模方程(模7),所以在高斯消元的过程中遇到除法要转换成乘上逆元. #include <cstdio> #include <cs

UVA 10679 I love Strings!!!(AC自动机)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620 题意: 给出一个文本串和若干个模式串,问模式串是否在文本串中出现过. 分析: 简单粗暴的AC自动机模板题,要注意模式串可能有重复的情况. /* * * Author : fcbruce * * Time : Sat 04 Oct 2014 03:30:15 PM CST * */ #i

UVA 1564 - Widget Factory(高斯消元)

UVA 1564 - Widget Factory 题目链接 题意:n种零件, 给定m个制作时间,每段时间制作k个零件,每种零件有一个制作时间,每段时间用Mon到Sun表示,求每个零件的制作时间,还要判断一下多解和无解的情况 思路:对于每段时间列出一个方程,这样一共列出m个方程解n个变元,利用高斯消元去求解,注意每个方程都是MOD 7的,所以在高斯消元过程中遇到除法要求该数字%7的逆元去进行运算 代码: #include <cstdio> #include <cstring> #i

UVa 10152 - ShellSort 题解

按他的方法排序,每次移动一个数到顶点,排成需要的序列. Problem D: ShellSort He made each turtle stand on another one's back And he piled them all up in a nine-turtle stack. And then Yertle climbed up. He sat down on the pile. What a wonderful view! He could see 'most a mile! T

ShellSort uva

ShellSort He made each turtle stand on another one's back And he piled them all up in a nine-turtle stack. And then Yertle climbed up. He sat down on the pile. What a wonderful view! He could see 'most a mile! The Problem King Yertle wishes to rearra

UVA ShellSort

题目如下: Problem D: ShellSort He made each turtle stand on another one's back And he piled them all up in a nine-turtle stack. And then Yertle climbed up. He sat down on the pile. What a wonderful view! He could see 'most a mile! The Problem King Yertle

UVA 562 Dividing coins --01背包的变形

01背包的变形. 先算出硬币面值的总和,然后此题变成求背包容量为V=sum/2时,能装的最多的硬币,然后将剩余的面值和它相减取一个绝对值就是最小的差值. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 50007 int c[102],d

UVA 10341 Solve It

Problem F Solve It Input: standard input Output: standard output Time Limit: 1 second Memory Limit: 32 MB Solve the equation: p*e-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0 where 0 <= x <= 1. Input Input consists of multiple test cases and te