【HNOI】trust 弦图最大独立集

　　【题目描述】有n个人，每个人之间都有是否信任的关系，要求找出k个人，使得k个人之间彼此信任，且k最大，保证不信任的关系由多个三元环组成，且三元环之间只可能有公共点，没有公共边，且不存在任意一个节点不属于任意一个三元环。

　　【数据范围】

　　　　n<=2000。

　　首先我们可以建立信任关系的反图，这样的出的图为弦图，那么我们只需要求出各个块的完美消除序列，然后再通过完美消除序列求出该图的最大独立集就可以了。

　　反思：开始脑残求的是最小染色，然后算的相同颜色的数量取max。

//By BLADEVIL
#include <cstdio>
#include <cstring>
#define maxn 2010

using namespace std;

int n,l;
int other[maxn*maxn],pre[maxn*maxn],last[maxn],flag[maxn],size[maxn],ans[maxn],que[maxn];

void connect(int x,int y) {
    pre[++l]=last[x];
    last[x]=l;
    other[l]=y;
}

int main() {
    freopen("trust.in","r",stdin); freopen("trust.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) {
            int x; scanf("%d",&x);
            if (!x) connect(i,j);
        }
    for (int i=n;i;i--) {
        int cur=0;
        for (int j=1;j<=n;j++) if ((size[j]>=size[cur])&&(!flag[j])) cur=j;
        que[i]=cur; flag[cur]=1;
        for (int p=last[cur];p;p=pre[p]) size[other[p]]++;
    }
    //for (int i=1;i<=n;i++) printf("%d ",que[i]); printf("\n");
    memset(flag,0,sizeof flag);
    for (int i=1;i<=n;i++) {
        int cur=que[i];
        if (flag[cur]) continue;
        ans[++ans[0]]=cur;
        for (int p=last[cur];p;p=pre[p]) flag[other[p]]=1;
    }
    printf("%d\n",ans[0]);
    for (int i=1;i<=ans[0];i++) printf("%d ",ans[i]); printf("\n");
    fclose(stdin); fclose(stdout);
    return 0;
}

【HNOI】trust 弦图最大独立集

推荐阅读