2-sat Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals) D

http://codeforces.com/contest/782/problem/D

题意：

每个队有两种队名，问有没有满足以下两个条件的命名方法：

①任意两个队的名字不相同。

②若某个队 A

思路：

学习了2-sat发现这题这么简单= =。

如果那天A了这题就前200了

//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha
")
/*
另第一个名字为a，第二个名字为b
一：
如果ai = aj，那么只能选择第二个
①如果bi = bj，那么无解
②如果bi != bj，那么两者之间连接一条边
上面是分类讨论

二：
如果ai != aj

*/
const int maxn = 2000 + 5;
struct TwoSAT{
    int n;
    vector<int> G[maxn * 2];
    bool mark[maxn * 2];
    int c, s[maxn * 2];///c是表示目前dfs到的个数和已经被标记的集合s
    bool dfs(int x){
        if (mark[x ^ 1]) return false;
        if (mark[x]) return true;
        mark[x] = true;
        s[c++] = x;
        for (int i = 0; i < G[x].size(); i++)
            if (!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n){
        this->n = n;
        for (int i = 0; i < 2 * n; i++) G[i].clear();
        memset(mark, 0, sizeof(mark));
    }
    ///利用题目条件找到x和y，即假设x1[0] | x2[1] = false;即：x1[0]|!x2[1]=false
    ///那么我们反转该条件：即x1[1]|!x2[0] = true,即两者任意一个成立即为true
    ///那么我们只要交叉建图即可
    void addedge(int x, int y){
        G[x].pb(y);
    }

    bool solve(){
        for (int i = 0; i < 2 * n; i += 2){
            if (!mark[i] && !mark[i + 1]){
                c = 0;
                if (!dfs(i)){
                    while (c) mark[s[--c]] = false;
                    if (!dfs(i + 1)) return false;
                }
            }
        }
        return true;
    }
};
TwoSAT tar;
int n;
pair<string, string> p[maxn];
char a[100], b[100];

bool solve(){
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            if (p[i].fi == p[j].fi){
                if (p[i].se == p[j].se) return false;
                else
                    tar.addedge(i*2, i*2+1), tar.addedge(j*2, j*2+1);
            }
            else {
                if (p[i].fi == p[j].se){
                    tar.addedge(i*2, j*2), tar.addedge(j*2+1, i*2+1);
                }
                if (p[i].se == p[j].fi){
                    tar.addedge(i*2+1, j*2+1), tar.addedge(j*2, i*2);
                }
                if (p[i].se == p[j].se){
                    tar.addedge(i*2+1, j*2), tar.addedge(j*2+1, i*2);
                }
            }
        }
    }
    if (!tar.solve()) return false;
    puts("YES");
    for (int i = 0; i < 2 * n; i += 2){
        if (tar.mark[i]){
            cout << p[i/2].fi << endl;
        }
        else {
            cout << p[i/2].se << endl;
        }
    }
    return true;
}

int main(){
    cin >> n;
    tar.init(n);
    for (int i = 0; i < n; i++){
        scanf("%s%s", a, b);
        p[i].fi = p[i].fi + a[0] + a[1] + a[2];
        p[i].se = p[i].se + a[0] + a[1] + b[0];
    }
    if (!solve()) puts("NO");
    return 0;
}

View Code