题意：有A、B、C3个任务分配给n个宇航员，其中每个宇航员恰好分配一个任务。假设n个宇航员的平均年龄为x，只有年龄大于x的才能领取A任务；只有年龄严格小于x的才能领取B任务，而任务C没有限制。有m对宇航员相互讨厌，因此不能分配同一任务。求出是否能找出符合的任务方案。（转自http://blog.csdn.net/u011345461/article/details/39779721）
题目看上去是ABC三个选择，实际上每个人只有两个选择。对于每对矛盾，如果两个人选择相同（即均为BC或均为AC），那么一个选C另一个必选B（A），另一个选C一个必选B（A），一个选B（A）另一个必选C，另一个选B（A）一个必选C；如果两个人选择不同（一个AC一个BC），那么一个选C另一个必选B，另一个选C一个必选A。
这题数据范围很大，好奇nm做法是怎么水过去的。。
正解是tarjan缩点，标记每个块的对立块，建立反图，对反图top排序，对于当前的块x,删除对立块和对立块在反图上的出边，并把当前快入队。最后看队列里没被删除的块即为答案块。把点扫一扫看看在不在答案块，在的话这个点的值代表选A（B）还是选C就是这个人的选择
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
template<class T>
inline void swap(T &a, T &b)
{
T tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = + ;
struct Edge
{
int u,v,nxt;
Edge(int _u, int _v, int _nxt){u = _u;v = _v;nxt = _nxt;}
Edge(){}
}edge1[MAXN << ], edge2[MAXN << ];
int head1[MAXN], head2[MAXN], vis[MAXN], tag[MAXN], rebelong[MAXN], del[MAXN], q[MAXN], he, ta, indeg[MAXN], cnt1, cnt2, n, m, belong[MAXN], group, b[MAXN], bb[MAXN], dfn[MAXN], stack[MAXN], top, low[MAXN], dfst, year[MAXN], x, tmp1, tmp2;
inline void insert1(int a, int b){edge1[++ cnt1] = Edge(a, b, head1[a]), head1[a] = cnt1;}
inline void insert2(int a, int b){edge2[++ cnt2] = Edge(a, b, head2[a]), head2[a] = cnt2;}
void dfs(int u)
{
b[u] = bb[u] = , dfn[u] = low[u] = ++ dfst, stack[++ top] = u;
for(int pos = head1[u];pos;pos = edge1[pos].nxt)
{
int v = edge1[pos].v;
if(!b[v]) dfs(v), low[u] = min(low[u], low[v]);
else if(bb[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
int now = -;++ group;
while(now != u) now = stack[top --], bb[now] = , belong[now] = group;
}
}
void rebuild()
{
memset(indeg, , sizeof(indeg)), memset(head2, , sizeof(head2));
for(int i = ;i <= cnt1;++ i)
if(belong[edge1[i].u] != belong[edge1[i].v])
insert2(belong[edge1[i].v], belong[edge1[i].u]), ++ indeg[belong[edge1[i].u]];
}
void tarjan()
{
memset(belong, , sizeof(belong)), memset(dfn, , sizeof(dfn)), memset(low, , sizeof(low)), group = , memset(b, , sizeof(b)), memset(bb, , sizeof(bb)), dfst = , top = , memset(rebelong, , sizeof(rebelong));
for(int i = ;i <= n;++ i) if(!b[i << ]) dfs(i << );
for(int i = ;i <= n;++ i) if(!b[i << | ]) dfs(i << | );
for(int i = ;i <= n;++ i) rebelong[belong[i << ]] = belong[i << | ], rebelong[belong[i << | ]] = belong[i << ];
rebuild();
}
void top_sort()
{
he = , ta = , memset(del, , sizeof(del));
for(int i = ;i <= group;++ i) if(!indeg[i]) q[ta ++] = i;
while(he < ta)
{
int now = q[he ++], renow = rebelong[now];
if(del[now]) continue; del[renow] = ;
for(int pos = head2[renow];pos;pos = edge2[pos].nxt)
{
int v = edge2[pos].v;
del[v] = ;
for(int poss = head2[v];poss;poss = edge2[poss].nxt) -- indeg[edge2[poss].v];
}
for(int pos = head2[now];pos;pos = edge2[pos].nxt)
{
int v = edge2[pos].v;
if(del[v]) continue;
-- indeg[v];
if(!indeg[v]) q[ta ++] = v;
}
}
}
int main()
{
while(scanf("%d %d", &n, &m) != EOF && n && m)
{
cnt1 = , memset(head1, , sizeof(head1)), x = ;
for(int i = ;i <= n;++ i) read(year[i]), x += year[i];
if(x % n == ) x = x / n;
else x = x / n + ;
for(int i = ;i <= n;++ i) year[i] = year[i] >= x; //year[i] = 1 表示选A或C year[i] = 0 表示选B或C
for(int i = ;i <= m;++ i)
{
read(tmp1), read(tmp2);
if(year[tmp1] == year[tmp2]) insert1(tmp1 << | , tmp2 << ), insert1(tmp2 << | , tmp1 << ), insert1(tmp1 << , tmp2 << | ), insert1(tmp2 << , tmp1 << | );
else insert1(tmp1 << | , tmp2 << ), insert1(tmp2 << | , tmp1 << );
}
tarjan();
int flag = ;
for(int i = ;i <= n;++ i) if(belong[i << | ] == belong[i << ]) flag = ;
if(flag)
{
printf("No solution.\n");
continue;
}
top_sort();
memset(vis, , sizeof(vis)), memset(tag, , sizeof(tag));
for(int i = ;i < ta;++ i) if(!del[q[i]]) vis[q[i]] = ;
for(int i = ;i <= n;++ i)
if(vis[belong[i << ]]) tag[i] = ;
else tag[i] = ;
for(int i = ;i <= n;++ i)
if(year[i] && !tag[i]) printf("A\n");
else if(!year[i] && !tag[i]) printf("B\n");
else printf("C\n");
}
return ;
}
UVA1391/LA3713