栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 1518 This Sentence is False

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 1518 This Sentence is False

#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;#define maxn 2010void makeset(int f[], int a){    f[a]=a;}int find(int f[], int a){    if (f[a]==a) return a;    return f[a]=find(f, f[a]);}bool same(int f[], int a, int b){    return find(f,a)==find(f,b);}void setunion(int f[], int a, int b){    f[find(f,a)]=find(f,b);}bool sentence(int n, int f[], int i, int t, char tf){    if (tf=='f')      {        if (same(f, i, t) || same(f, i+n, t+n)) return false;        setunion(f, i, n+t);        setunion(f, t, n+i);    }    else    {        if (same(f, i, n+t) || same(f, t, n+i)) return false;        setunion(f, i, t);        setunion(f, i+n, t+n);    }    return true;}void printans(int n, int f[]){    int root1, root2, cal1, cal2, ans=0;    bool v[maxn]={0};    for (int i=0; i<n; i++)    {        if (same(f, i, n+i))        { printf("Inconsistentn"); return;        }        if (!v[i] && !v[i+n])        { root1=find(f, i); root2=find(f, i+n); cal1=1; cal2=0; v[i]=v[i+n]=1; for (int j=0; j<2*n; j++)     if (!v[j])     {         if (same(f, root1, j)){v[j]=1;if(j<n)cal1++;}         else if (same(f, root2, j)){v[j]=1;if(j<n)cal2++;}     } ans+=(cal1>cal2)?cal1:cal2;        }    }    printf("%dn", ans);}int main(){    int n, t;    int f[maxn];    char str[100];    char s1[20], s2[20], s3[20];    bool inconsistent;    while (scanf("%d", &n)==1 && n)    {        gets(str);        for (int i=0; i<2*n; i++)        makeset(f, i);        inconsistent=false;        for (int i=0; i<n; i++)        { scanf("%s %d %s %s", s1, &t, s2, s3); if (!inconsistent && !sentence(n, f, i, t-1, s3[0]))     inconsistent=true;        }        if (inconsistent) printf("Inconsistentn");        else printans(n, f);    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379490.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号