UVALive 3713 Astronauts

UVALive 3713 Astronauts

題意：

有n個宇航員 他們需要完成A、B、C三種任務 年齡>=平均年齡的人可以做A和C 年齡<平均年齡的能做B和C 且宇航員之間有討厭關系不能一起做任務 要求給出一種分配方案

思路：

一類人有2種選擇而且必須選1個 因此想到2-sat 根據年齡和討厭關系來建邊 之後先做可行性判斷 確定可以後 求出任意一組可行解 不需要字典序最小

代碼：

#include
#include
#include
#include
using namespace std;
#define N 200010

struct edge
{
    int u,v,next;
}ed[N*4];
int n,m,tot,top,cnt,idx;
int dfn[N],low[N],st[N],instack[N],belong[N],head[N],f[N],col[N],in[N],qu[N],opt[N];

void tarjan(int u)
{
    int i,v;
    dfn[u]=low[u]=++idx;
    instack[u]=1;
    st[++top]=u;
    for(i=head[u];~i;i=ed[i].next)
    {
        v=ed[i].v;
        if(dfn[v]==-1)
        {
            tarjan(v);
			low[u]=min(low[u],low[v]);
        }
        else if(instack[v]&&dfn[v]>1);
        for(i=0;itmp) f[i]=1;
            else f[i]=2;
            f[i+1]=3;
        }
        if(can())
        {
            solve();
            for(i=0;i