2011.08.17

POJ  3678  Katu Puzzle

        题意：有n个位置可以填0和1，给出m个逻辑表达式描述了zhi[a] op zhi[b]=c的关系，给出a,b,c,op。其中ai,bi,ci是0或1，op是逻辑运算符AND，OR和XOR。问是否有一个n元素的数组zhi[ ]可以满足全部m个表达式。有则输出"YES"，否则输出"NO"。

        解题：相当标准的2-SAT问题。重点是理解2-SAT的建图主要是根据矛盾则向矛盾的另一方连边，以及对偶边，而不管当前取值是否也与另一方矛盾。

#include
#include
#include
#include
#define MV 1005
#define ME 1000005
using namespace std;
struct edge
{int v,next;
}g[ME],gt[ME],tree[ME];
int n,m,cnt,ID,p1,p2,id[MV],tree_cnt,order[MV],indegree[MV],color[MV],h1[MV],h2[MV];
bool used[MV],used_tree[MV][MV];
void add(int u,int v)
{g[p1].v=v;g[p1].next=h1[u];h1[u]=p1++;g[p1].v=u^1;          //对偶边g[p1].next=h1[v^1];h1[v^1]=p1++;gt[p2].v=u;           //反向边gt[p2].next=h2[v];h2[v]=p2++;gt[p2].v=v^1;         //对偶边的反向边gt[p2].next=h2[u^1];h2[u^1]=p2++;
}void init()
{p1=p2=1;memset(h1,-1,sizeof(h1));memset(h2,-1,sizeof(h2));
}void build_graph()
{int a,b,c;string s;char op[10];scanf("%d%d",&n,&m);while(m--){scanf("%d %d %d %s\n",&a,&b,&c,op);s=op;if(s=="AND" && c==1){add(2*a,2*b);add(2*a,2*b+1);add(2*a+1,2*b+1);}else if(s=="AND" && c==0){add(2*a+1,2*b);}else if(s=="OR" && c==1){add(2*a,2*b+1);}else if(s=="OR" && c==0){add(2*a,2*b);add(2*a+1,2*b);add(2*a+1,2*b+1);}else if(s=="XOR" && c==1){add(2*a,2*b+1);add(2*a+1,2*b);}else if(s=="XOR" && c==0){add(2*a,2*b);add(2*a+1,2*b+1);}}
}void dfs1(int u)
{used[u]=1;for(int i=h1[u];i!=-1;i=g[i].next)if(!used[g[i].v])dfs1(g[i].v);order[cnt++]=u;
}void dfs2(int u)
{used[u]=1;id[u]=ID;for(int i=h2[u];i!=-1;i=gt[i].next)if(!used[gt[i].v])dfs2(gt[i].v);
}void scc()
{memset(used,0,sizeof(used));cnt=0;for(int i=0;i<2*n;i++)if(!used[i]) dfs1(i);memset(used,0,sizeof(used));ID=0;for(int i=cnt-1;i>=0;i--)if(!used[order[i]]){ID++;dfs2(order[i]);}
}bool sat_judge()
{for(int i=0;i<2*n;i+=2)if(id[i]==id[i+1])return 0;return 1;
}int main()
{init();build_graph();scc();if(sat_judge()) printf("YES\n");else printf("NO\n");return 0;
}

HDU  3940  The Angry  Birds  

        题意:

#include
#include
#include
#include
#include
using namespace std;
const double g=9.8;
double h;
char c[10];
string s;void red()
{double vx,vy,s;scanf("%lf%lf",&vx,&vy);s=vx*(vy/g+sqrt(2*h/g+vy*vy/g/g));printf("%.3lf\n",s);
}void yellow()
{double vx,vy,s,t1,t2,t3,t,h1,h2;scanf("%lf%lf%lf",&vx,&vy,&t);t1=vy/g;t2=sqrt(2*(h+vy*vy/2/g)/g);if(t1+t2

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！