bzoj 1242 弦图判定 MCS

题目大意:

给定一张无向图,判断是不是弦图.

题解:

今天刚学了《弦图与区间图》

本来写了一个60行+的学习笔记

结果因为忘了保存重启电脑后被还原了...

那就算了吧.

MCS最大势算法,写起来挺愉悦的.

不过觉得除了做裸题就只能做裸题了..

直接贴板子

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;static char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

#define rg register int

#define rep(i,a,b) for(rg i=(a);i<=(b);++i)

#define per(i,a,b) for(rg i=(a);i>=(b);--i)

const int maxn = 1024;

const int maxm = maxn*maxn;

struct Edge{

    int next,to;

}G[maxm];

int head[maxn],cnt;

void add(int u,int v){

    G[++cnt].to = v;

    G[cnt].next = head[u];

    head[u] = cnt;

}

vector<int>ws[maxn];

int seq[maxn],lab[maxn],pos[maxn];

bool map[maxn][maxn];

int main(){

    int n,m;read(n);read(m);

    int u,v;

    rep(i,1,m){

        read(u);read(v);

        map[u][v] = map[v][u] = true;

        add(u,v);add(v,u);

    }

    rep(i,1,n) ws[0].push_back(i);

    int nw = 0;

    per(i,n,1){

        while(1){

            u = ws[nw].back();

            if(pos[u]) ws[nw].pop_back();

            else break;

            while(ws[nw].empty()) -- nw;

        }

        pos[u] = i;seq[i] = u;

        for(int p = head[u];p;p=G[p].next){

            ++ lab[G[p].to];

            nw = max(nw,lab[G[p].to]);

            ws[lab[G[p].to]].push_back(G[p].to);

        }

    }

    bool flag = false;

    per(i,n,1){

        u = seq[i];

        v = -1;

        for(int i = head[u];i;i=G[i].next){

            if(pos[G[i].to] < pos[u]) continue;

            if(v == -1 || (pos[v] > pos[G[i].to])) v = G[i].to;

        }

        for(int i = head[u];i;i=G[i].next){

            if(pos[G[i].to] < pos[u]) continue;

            if(v != G[i].to && !map[v][G[i].to]){

                flag = true;

                break;

            }

        }

        if(flag) break;

    }

    puts(flag ? "Imperfect" : "Perfect");

    return 0;

}

巴特西

bzoj 1242 弦图判定 MCS

题目大意:

题解:

最新文章

热门文章