首页 > 代码库 > 【poj2942】 Knights of the Round Table
【poj2942】 Knights of the Round Table
http://poj.org/problem?id=2942 (题目链接)
题意
有n个骑士要去参加圆桌会议，他们将围成一圈，想要他们不打架，当且仅当参加圆桌会议的骑士数为奇数并且相邻的两个骑士不互相憎恨。现在给出m条骑士之间两两憎恨的关系，问有多少骑士无论在何种情况下都不能参加圆桌会议。
Solution
思路到是很简单，先构出原图的补图，补图中每条边代表这两个骑士可以相邻。那么很显然，如果某一个骑士处于任意一个奇环中，那么他就可以参加会议。
这个问题该怎么处理呢？我们用Tarjan求出点-双连通分量，对于每一个点双，通过黑白染色看是否存在奇环，若染色不成功，那么存在奇环，否则是偶环。
细节
Tarjan真是恶心爆。。求点-双一定要存边，这样可以避免很多分类讨论。。。
代码
// bzoj1013#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#define LL long long#define inf 2147483640#define eps 1e-7#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;inline int gi() { int x=0,f=1;char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=1010,maxm=1000010;struct edge {int to,next;}e[maxm<<1];struct data {int u,v;}s[maxn];int vis[maxn],dfn[maxn],low[maxn],f[maxn][maxn],pos[maxn];int ind,cnt,top,n,m,num,p,id[maxn],head[maxn];vector<int> v[maxn];void link(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void Init() { for (int i=1;i<=num;i++) v[i].clear(); cnt=ind=top=num=0; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(pos,0,sizeof(pos)); memset(id,0,sizeof(id)); memset(f,0,sizeof(f));}void Tarjan(int x,int fa) { dfn[x]=low[x]=++ind; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) { if (!dfn[e[i].to]) { s[++top]=(data){x,e[i].to}; Tarjan(e[i].to,x); low[x]=min(low[x],low[e[i].to]); if (low[e[i].to]>=dfn[x]) { num++; while (1) { v[num].push_back(s[top].u);v[num].push_back(s[top].v); if (s[top].u==x && s[top].v==e[i].to) break; top--; } top--; } } else low[x]=min(low[x],dfn[e[i].to]); }}bool dfs(int x,int col) { id[x]=col; for (int i=head[x];i;i=e[i].next) if (pos[e[i].to]==p) { if (!id[e[i].to]) { if (!dfs(e[i].to,col^1)) return 0; } else if (id[e[i].to]==id[x]) return 0; } return 1;}void work(int x) { vis[x]=1; for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to] && pos[e[i].to]==p) work(e[i].to);}int main() { while (1) { n=gi(),m=gi(); if (!n && !m) break; Init(); for (int x,y,i=1;i<=m;i++) { x=gi(),y=gi(); f[x][y]=f[y][x]=1; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j && !f[i][j]) link(i,j); for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i,0); for (p=1;p<=num;p++) { for (int j=0;j<v[p].size();j++) pos[v[p][j]]=p; if (!dfs(v[p][0],p*2)) work(v[p][0]); } int ans=0; for (int i=1;i<=n;i++) if (!vis[i]) ans++; printf("%d\n",ans); } return 0;}
【poj2942】 Knights of the Round Table
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。