当前位置：凯发ag旗舰厅登录网址下载 > > 编程问答 >内容正文

编程问答

hdu 1814 peaceful commission -凯发ag旗舰厅登录网址下载

发布时间：2025/1/21 编程问答 5 豆豆

凯发ag旗舰厅登录网址下载收集整理的这篇文章主要介绍了 hdu 1814 peaceful commission 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

2-sat，输出字典序最小的解，白书模板。

//twosat输出字典序最小的解的模板 //注意：0,1是一组，1,2是一组..... #include #include #include #include #include using namespace std;const int maxn=8000 5; int m;struct twosat {int n;vector<int> g[maxn*2];bool mark[maxn*2];int s[maxn*2],c;bool dfs(int x){if(mark[x^1]) return false;if(mark[x]) return true;mark[x]=true;s[c ]=x;for(int i=0;i)if(!dfs(g[x][i])) return false;return true;}void init(int n){this->n=n;for(int i=0;i2;i ) g[i].clear();memset(mark,0,sizeof mark);}void add_clause(int x,int y){g[x].push_back(y^1);g[y].push_back(x^1);}bool solve(){for(int i=0;i<2*n;i =2)if(!mark[i]&&!mark[i 1]){c=0;if(!dfs(i)){while(c>0) mark[s[--c]]=false;if(!dfs(i 1)) return false;}}return true;}//输出字典序最小的解void printf(){for(int i=0;i){if(mark[2*i]) printf("%d\n",2*i 1);else printf("%d\n",2*i 1 1);}} };int main() {twosat t;while(~scanf("%d%d",&t.n,&m)){t.init(t.n);for(int i=0;i){int a,b;scanf("%d%d",&a,&b);a--;b--;t.add_clause(a,b);}if(t.solve()) t.printf();else printf("nie\n");}return 0; }

转载于:https://www.cnblogs.com/zufezzt/p/4906130.html

总结

以上是凯发ag旗舰厅登录网址下载为你收集整理的hdu 1814 peaceful commission的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。