[POI2001] 和平委员会
题意:
一共 \(n\) 个党派,\(2i-1\) 和 \(2i\) 在同一个党派。要求:每个党派必须且只能派一个人,而且有 \(m\) 个限制条件,要求 \(i\) 和 \(j\) 不能同时出现。
求解派的人的编号,不成立输出 NIE
分析:
对于这句话:
每个党派必须且只能派一个人
这个条件的满足要求就是:两个人 \(2i-1\) 和 \(2i\) 不在同一个缩点里就行。
要求 \(i\) 和 \(j\) 不能同时出现。
这个表示成布尔方程的形式就是:
\[(\neg i \vee \neg j) \]要求每个党派派一个,当 \(i\) 派出,应当派出 \(j\) 的搭档。同理 \(j\)
因此,我们应该从 \(i\rightarrow \neg j\),\(j\rightarrow \neg i\) 建立边。
也就是,将 该点 和 对方同党派另一个人 相连。
跑缩点,然后按照拓扑序大小,比较同党派之间的 \(dfs\) 序大小,输出 \(dfs\) 序小的人即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6+5;
int dfn[N],low[N],sd[N],idx,vis[N],cnt,sta[N],top;
vector<int> g[N];
int get(int x){
return ((x%2)?x+1:x-1);
}
void tarjan(int x){
dfn[x]=low[x]=++cnt;
sta[++top]=x; vis[x]=1;
for(auto y:g[x]){
if(!dfn[y]){tarjan(y); low[x]=min(low[x],low[y]);}
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
idx++; int y;while(y=sta[top--]){
sd[y]=idx; vis[y]=0;
if(x==y) break;
}
}
}
int main(){
cin>>n>>m;
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
g[x].push_back(get(y)); g[y].push_back(get(x));
}
for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=2*n;i++){
if(i%2==1&&sd[i]==sd[i+1]){puts("NIE"); return 0;}
}
for(int i=1;i<=2*n;i++){
if(sd[i]<sd[get(i)]) printf("%d\n",i);
}
system("pause");
return 0;
}