B - Let's go home
Crawling in process...
Crawling failed
Time Limit:1000MS
Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
Description
小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。
―― 余光中
―― 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
Input
第一行有两个整数,T和M,1<=T<=1000表示队伍数,1<=M<=5000表示对数。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
Output
可行输出yes,否则输出no,以EOF为结束。
Sample Input
1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4
Sample Output
yes no也是几乎模板,就是需要合并分解下范式。#include<cstdio> #include<cstring> #include<iostream> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define clr(f,z) memset(f,z,sizeof(f)) using namespace std; const int mm=6010; class Edge { public:int v,next; }; class TWO_SAT { public: int dfn[mm],e_to[mm],stack[mm]; Edge e[mm*50]; int edge,head[mm],top,dfs_clock,bcc; void clear() { edge=0;clr(head,-1); } void add(int u,int v) { e[edge].v=v;e[edge].next=head[u];head[u]=edge++; } void add_my(int x,int xval,int y,int yval) { x=x+x+xval;y=y+y+yval; add(x,y); } void add_clause(int x,int xval,int y,int yval) {///x or y x=x+x+xval; y=y+y+yval; add(x^1,y);add(y^1,x); } int tarjan(int u) { int lowu,lowv; lowu=dfn[u]=++dfs_clock; int v; stack[top++]=u; for(int i=head[u];~i;i=e[i].next) { v=e[i].v; if(!dfn[v]) { lowv=tarjan(v); lowu=min(lowv,lowu); } else if(e_to[v]==-1)//in stack lowu=min(lowu,dfn[v]); } if(dfn[u]==lowu) { ++bcc; do{ v=stack[--top]; e_to[v]=bcc; }while(v!=u); } return lowu; } bool find_bcc(int n) { clr(e_to,-1); clr(dfn,0); bcc=dfs_clock=top=0; FOR(i,0,2*n-1) if(!dfn[i]) tarjan(i); for(int i=0;i<2*n;i+=2) if(e_to[i]==e_to[i^1])return 0; return 1; } }two; int n,m; int main() { int a,b,c,d; while(~scanf("%d%d",&n,&m)) { two.clear(); FOR(i,1,n) { scanf("%d%d%d",&a,&b,&c); two.add_clause(a,1,b,1);//a or (b and c) two.add_clause(a,1,c,1); } FOR(i,1,m) { scanf("%d%d",&a,&b); two.add_clause(a,0,b,0);//!a->b } if(two.find_bcc(n*3))printf("yes\n"); else printf("no\n"); } return 0; }