首页 > 代码库 > UVALive3713_Astronauts

UVALive3713_Astronauts

2024-07-13 06:08:25   216人阅读

有n个宇航员，根据年龄限制，所有宇航员只能从事A或B中的一种任务，所有人都可以从事C的任务。有的宇航员之间相互讨厌，不能分在一组，求出一种满足条件的分配方案。

2sat。mark[]中i+i和i+i+1分别表示i从事C工作或者他的特有工作。

对于仇恨关系，我们可以知道U和V两个人不能同时从事C工作。于是加边 (U+U,V+V+1),(V+V,U+U+1)。

同时，如果这两个人的特有工作相同，那么还需要加边(U+U+1,V+V),(V+V+1,U+U)。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 5555550using namespace std;int age[maxn],n,m;int next[maxn],to[maxn],first[maxn],edge;bool mark[maxn];//0 C \ 1 A|Bint Q[maxn],top;double avg;void addedge(int U,int V){    edge++;    to[edge]=V,next[edge]=first[U],first[U]=edge;}bool dfs(int cur){    if (mark[cur^1]) return false;    if (mark[cur]) return true;    Q[++top]=cur,mark[cur]=true;    for (int i=first[cur]; i!=-1; i=next[i])        if (!dfs(to[i])) return false;    return true;}int main(){    int U,V;    while (scanf("%d%d",&n,&m) && (n|m))    {        avg=0,edge=-1;        for (int i=1; i<=n; i++)        {            scanf("%d",&age[i]);            avg+=age[i];            mark[i+i]=mark[i+i+1]=false;            first[i+i]=first[i+i+1]=-1;        }        avg/=n;        while (m--)        {            scanf("%d%d",&U,&V);            addedge(U+U,V+V+1),addedge(V+V,U+U+1);            if ((age[U]<avg)^(age[V]<avg)) continue;            addedge(U+U+1,V+V),addedge(V+V+1,U+U);        }        bool flag=true;        for (int i=1; i<=n; i++)        {            if (mark[i+i] || mark[i+i+1]) continue;            top=0;            if (!dfs(i+i))            {                while (top) mark[Q[top--]]=false;                if (!dfs(i+i+1))                {                    flag=false;                    break;                }            }        }        if (flag)        {            for (int i=1; i<=n; i++)                if (mark[i+i]) printf("C\n");                    else printf("%c\n",age[i]>=avg?‘A‘:‘B‘);        }        else puts("No solution.");    }    return 0;}


联系
我们