【HDU】1814 Peaceful Commission


http://acm.hdu.edu.cn/showproblem.php?pid=1814

题意:n个2人组,编号分别为2n和2n+1,每个组选一个人出来,且给出m条关系(x,y)使得选了x就不能选y,问是否能从每个组选出1人。且输出字典序最小的答案。(n<=8000, m<=20000)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=8005, M=20005;
struct E { int next, to; }e[M<<1];
int cnt, ihead[N<<1], top, s[N<<1], n, m;
bool vis[N<<1];
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
bool dfs(int x) {
	if(vis[x^1]) return 0;
	if(vis[x]) return 1;
	vis[x]=1;
	s[++top]=x;
	for(int i=ihead[x]; i; i=e[i].next) if(!dfs(e[i].to)) return 0;
	return 1;
}
bool work() {
	int nn=n<<1;
	for(int i=0; i<nn; i+=2) if(!vis[i] && !vis[i+1]) {
		top=0;
		if(!dfs(i)) {
			while(top) vis[s[top--]]=0;
			if(!dfs(i+1)) return 0;
		}
	}
	for(int i=0; i<nn; ++i) if(vis[i]) printf("%d\n", i+1);
	return 1;
}
int main() {
	while(~scanf("%d%d", &n, &m)) {
		for(int i=0; i<m; ++i) { int x, y; scanf("%d%d", &x, &y); --x; --y; add(x, y^1); add(y, x^1); }
		if(!work()) puts("NIE");
		cnt=top=0;
		memset(vis, 0, sizeof(bool)*(n<<1));
		memset(ihead, 0, sizeof(int)*(n<<1));
	}
	return 0;
}

  

本题很显然的2-sat问题= =

对于关系(x,y)实际上就是满足!(x & y)

即当x=1时y必须为0,即连边x->y'

当y=1时x必须为1,即连边y->x'

由于这个dfs的算法本身就是字典序最小了= =直接搞就行了= =

(妈呀难道这个算法是O(nm)的嘛QAQ看来得写tarjan了以后= =(虽然字典序最小只能用这个O(nm)算法= =?)

优质内容筛选与推荐>>
1、python之学习-------变量名
2、对于System.Net.Http的学习——System.Net.Http 简介
3、1
4、vim配置python编程环境及YouCompleteMe的安装教程
5、数据集与JSON对象互相转换


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号