题意：
有n个宇航员，按照年龄划分，年龄低于平均年龄的是年轻宇航员，而年龄大于等于平均年龄的是老练的宇航员。
现在要分配他们去A，B，C三个空间站，其中A站只有老练的宇航员才能去，而B站是只有年轻的才能去，C站都可以去。
有m对宇航员相互讨厌，不能让他们在同一个空间站工作。
输出每个宇航员应分配到哪个空间站，如果没有则输出No solution.
分析：
对于每个宇航员，有两种选择，（A,B）或C。第一个选择中取A还是取B取决于年龄。
构图，2-SAT找满足题意的方案再输出即可。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define Maxn 100010
#define Maxm 100010 int n,m;
int age[Maxn],first[*Maxn],mark[*Maxn],s[*Maxn];
int c,v; struct node
{
int x,y,next;
}t[*Maxm];int len; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} bool dfs(int x)
{
if(mark[x^]) return ;
if(mark[x]) return ;
mark[x]=;
s[++c]=x;
for(int i=first[x];i;i=t[i].next)
if(!dfs(t[i].y)) return ;
return ;
} bool solve()
{
memset(mark,,sizeof(mark));
for(int i=;i<n;i++)
if(!mark[*i]&&!mark[*i+])
{
c=;
if(!dfs(*i))
{
while(c>) mark[s[c--]]=;
if(!dfs(*i+)) return ;
}
}
return ;
} void output()
{
for(int i=;i<n;i++)
if(mark[i*+]) printf("C\n");
else if(age[i]*n>=v) printf("A\n");
else printf("B\n");
} int main()
{
while()
{ scanf("%d%d",&n,&m);
len=;v=;
if(n==&&m==) break;
memset(first,,sizeof(first));
for(int i=;i<n;i++) scanf("%d",&age[i]),v+=age[i];
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);x--;y--;
ins(x*+,y*);ins(y*+,x*);
if(!((age[x]*n>=v)^(age[y]*n>=v))) ins(x*,y*+),ins(y*,x*+);
}
if(!solve()) printf("No solution.\n");
else output();
}
return ;
}
[LA3713]
2016-03-18 13:19:17