hdu 1814 peaceful commission -凯发k8官方网
凯发k8官方网
收集整理的这篇文章主要介绍了
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
总结
以上是凯发k8官方网为你收集整理的hdu 1814 peaceful commission的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。
