2012年10月14日 星期日

Codeforces 228E The Road to Berland is Paved With Good Intentions

因為去兩次等於沒去,題目也沒問最小天,亂做即可

也就是只需判斷可不可以符合所有條件

條件是什麼?


if C(u, v) == 1, P(u)  = P(v)(即是 若P(u)則P(v)&若!P(v)則!P(v),反向亦可)
if C(u, v) == 0, P(u) != P(v) (同上)

C為有沒有上過柏油,P為要不要上柏油

所以,

Disjoint Set!

酷似2-SAT,但是無需用這麼複雜的方法

因為2-SAT其實是一個較廣泛,不論解單向或雙向的條件皆可的作法
如:『若A則B且若!A則!B,然後反向不一定有』

但這題既然是雙向,那何不用簡單的並查集呢?

//By momo
#include<cstdio>
#include<algorithm>
#define N 210
using namespace std;

int n, m, det[N], fa[N], ans[N];
void init(){ for(int i = 0; i < 2*n; i++) fa[i] = i; }
int find(int x){ return fa[x] = (fa[x]==x?x:find(fa[x])); }
void unio(int a, int b){ fa[find(a)] = find(b); }

int main(){
    
    scanf("%d%d", &n, &m);
    
    int flag = 0; init();
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c); a--, b--;
        if(c) unio(a, b),   unio(a+n, b+n);
        else  unio(a, b+n), unio(a+n, b);
        if(find(a) == find(a+n) || find(b) == find(b+n)) flag = 1;
    }
    if(flag) return puts("Impossible"), 0;
    
    for(int i = 0; i < n; i++){
        if(det[i] == 0){
            det[i] = 1;
            for(int j = 0; j < n; j++){
                if(find(i) == find(j)) det[i] = 1;
                if(find(i) == find(j+n)) det[i] = -1;
            }
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++) if(det[i] == 1) ans[cnt++] = i+1;
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) printf("%d%c", ans[i], i == cnt-1?'\n':' ');
}

2 則留言:

  1. 我知道你寫這篇只是為了嗆我寫2-SAT還沒寫不出來 xD

    回覆刪除
    回覆
    1. 我只是講給我自己聽,以免以後忘記而已==
      (( XP

      刪除