HDU 1814(染色)

题目大意

有n个党派，每个党派2个人，这2*n个人之间存在一些敌对关系，现在要从中选出n个人组成一个委员会，要求满足: 1.每个党派中选1个 2.委员会中不存在敌对关系

分析

题目中第i个党派的成员编号是2n-1与2n，我们将编号减去1就可以通过x^1来得到和x在相同党派的另一个人了。如果a与b敌对，那么a一定与b^1相同颜色。 用染色法来解决这个问题，设1为选中的颜色，2为不选的颜色。 这样我们从一个未被染色的节点x出发将它染为1，并通过深搜将和它颜色相同的节点y染为1,并将y ^1染为2. 如果出现矛盾则将从x节点出发的节点颜色全部清零，将x染为2看是否可行，若不可行则问题无解。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> #include<map> #include<algorithm> #include<set> #include<stack> using namespace std; const int MAXN=160005; const int MAXM=200005; int col[MAXN];//col[i]为1表示选中，为0表示不选 int now[MAXN];//保存当前轮染色过程中的节点编号 int cnt; int n,m; struct Edge { int v; int next; }edge[MAXM]; int edgecount; int head[MAXN]; void Init() { edgecount=0; memset(head,-1,sizeof(head)); } void Add_edge(int u,int v) { edge[++edgecount].v=v; edge[edgecount].next=head[u]; head[u]=edgecount; } bool Paint(int x)//染色成功返回1否则返回0 { if(col[x]==2)return 0; if(col[x]==1)return 1; col[x]=1;col[x^1]=2; now[++cnt]=x; for(int k=head[x];k!=-1;k=edge[k].next) { int v=edge[k].v; if(!Paint(v))return 0; } return 1; } bool Work()//如果存在可行解返回1否则返回0 { memset(col,0,sizeof(col)); for(int u=0;u<n*2;u++) { if(col[u])continue; cnt=0; if(!Paint(u)) { for(int j=1;j<=cnt;j++) { col[now[j]]=0; col[now[j]^1]=0; } if(!Paint(u^1)){return 0;} } } return 1; } int main() { int a,b; while(scanf("%d%d",&n,&m)!=EOF) { Init(); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); a--;b--; Add_edge(a,b^1); Add_edge(b,a^1); } memset(col,0,sizeof(col)); if(Work())//染色成功 { for(int i=0;i<n*2;i++) if(col[i]==1)cout<<i+1<<endl; } else cout<<"NIE"<<endl; } return 0; }