挑战程序设计竞赛p326例题 poj3683 (奶牛呢） 如果你还不了解布尔方程和蕴含式，请先移步蕴含式是什么和布尔方程简介，运算法则 有些很巧妙的地方和技巧、想要总结一下。 首先这题我们考虑到，每个仪式可以在开始或结束时举行，可以用一个有补的变量表示；这时想到了布尔变量,对于一个仪式，我们用 xi 表示它在刚开始时举行，若 !xi 则表示它在结束时举行。
我们对于不同时发生的区间记为 ¬xi∨¬xj 为什么这样呢？请看下面的真值表
xi xj ¬xi∨¬xj TTFTFTFTTFFT很明显，在不同时发生的仪式我们需要其中一个x 的值为false（即F） 而真值表证明了当且仅当两个仪式同时发生时， ¬xi∨¬xj 为false 这表明我们可以用 ¬xi∨¬xj 的真假表示两个仪式是否同时发生。
这样我们可以根据各区间的起点和终点得出形如这样的布尔公式
(xi∨xj)∧(¬xn∨¬xm)∧...... 使这个表达式值为真即可。那么我们如何将这个表示为图呢？ 根据公式
a∨b≡¬a→b∧¬b→a 在求解和之积式的布尔方程[真值指派使整个方程为真]（《挑战》p324）的问题中，我们知道对于式 a→b 可以形象表示为a到b的一条有向边，那么同样地在这个题中，我们把 a∨b 表示为 ¬a→b∧¬b→a 后按此方式建边即可。接下来是如何判断两仪式是否冲突的问题： 我们看到一个区间与另一个区间有交集，当且仅当两区间起点的最大值<终点最小值时成立，举例：区间 [1,5] 显然与 [2,4] 和 [2,7] 有交集，而它们都满足两区间起点的最大值<终点最小值，举个不满足的例子：区间 [1,3] 与 [4,6] 就不满足，它们确实没有交集。 那么我们只需要这样去判断，再根据情况去加边就好了。比如， s[i] ~( s[i]+d[i] )与( t[j]−d[j] ) ~ t[j] 有冲突（即有交集），那么表示 ¬xi∨xj 为true，假定我们用0~n表示 x1 ~ xn , n+1~2*n表示 ¬x1 到 ¬xn ,即 i→(j+n)∧(j+n)→(i+n) ,我们连边（i，j+n）和（j+n，i+n）。 这样再根据求布尔方程SAT问题的方法，我们就能解决这个题了。 代码
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> //AC using namespace std; const int maxn=2000; int s[maxn]; int t[maxn]; int d[maxn]; bool used[maxn]; vector<int > g[maxn]; vector<int > rg[maxn]; vector<int >vs; int rank[maxn]; int n; void addedge(int from,int to) { g[from].push_back(to); rg[to].push_back(from); } void dfs(int v) { used[v]=true; for(unsigned i=0;i<g[v].size();i++) { if(!used[g[v][i]]) { dfs(g[v][i]); } } vs.push_back(v); } void rdfs(int v,int k) { used[v]=true; rank[v]=k; for(unsigned i=0;i<rg[v].size();i++) { if(!used[rg[v][i]]) { rdfs(rg[v][i],k); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int h,m,tim; scanf("d:d",&h,&m); tim=h*60+m; s[i]=tim; scanf("d:d",&h,&m); tim=h*60+m; t[i]=tim; scanf("%d",&d[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<=n && j!=i;j++) { if(min(s[i]+d[i],s[j]+d[j])>max(s[i],s[j])) { //!xiV!xj=xi->!xj ^ xj->!xi addedge(i,n+j); addedge(j,n+i); } if(min(s[i]+d[i],t[j])>max(s[i],t[j]-d[j])) { //!xiVxj addedge(i,j); addedge(n+j,n+i); } if(min(s[j]+d[j],t[i])>max(s[j],t[i]-d[i])) { //!xjVxi addedge(j,i); addedge(n+i,n+j); } if(min(t[i],t[j])>max(t[i]-d[i],t[j]-d[j])) { //xiVxj addedge(n+i,j); addedge(n+j,i); } } } memset(used,0,sizeof(used)); vs.clear(); for(int i=1;i<=n;i++) { if(!used[i]) { dfs(i); } } int ruby=vs.size(); memset(used,0,sizeof(used)); int k=1; for(int i=ruby-1;i>=0;i--) { if(!used[vs[i]]) { rdfs(vs[i],k); k++; } } k--; for(int i=1;i<=n;i++) { if(rank[i]==rank[i+n]) { printf("NO\n"); return 0; } } printf("YES\n"); for(int i=1;i<=n;i++) { if(rank[i]>rank[n+i]) { printf("d:d d:d\n",s[i]/60,s[i]%60,(s[i]+d[i])/60,(s[i]+d[i])%60); } else { printf("d:d d:d\n",(t[i]-d[i])/60,(t[i]-d[i])%60,t[i]/60,t[i]%60); } } return 0; }如果你不了解布尔方程，看不懂上面的式子，先看布尔方程的介绍及运算法则和蕴含式的计算，介绍 qwq谢谢看到这里。。。。
