/* 2SAT，找出一組解 同3648注意一點(diǎn)的是，在最后輸入答案的時(shí)候犯了很多錯(cuò)誤。最后只輸出顏色為1的點(diǎn)如果沒有目標(biāo)點(diǎn)的話，就在下行找顏色為1的點(diǎn)像3648,需要找和新娘顏色一樣的點(diǎn)，新娘的顏色一定為1，但是其在上行，所以在上行中找顏色為1的點(diǎn) */// include file #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <ctime>#include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <bitset> #include <strstream>#include <algorithm> #include <string> #include <vector> #include <queue> #include <set> #include <list> #include <functional>using namespace std;// typedef typedef long long LL; typedef unsigned long long ULL;// #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout) #define FORi(a,b,c) for(int i=(a);i<(b);i+=c) #define FORj(a,b,c) for(int j=(a);j<(b);j+=c)#define FF(i,a) for(int i=0;i<(a);i+++) #define FFD(i,a) for(int i=(a)-1;i>=0;i--) #define Z(a) (a<<1) #define Y(a) (a>>1)const double eps = 1e-11; const double Pi = acos(-1.0);template<class T> inline T sqr(T a){return a*a;} template<class T> inline T TMAX(T x,T y) {if(x>y) return x;return y; } template<class T> inline T TMIN(T x,T y) {if(x<y) return x;return y; } template<class T> inline void SWAP(T &x,T &y) {T t = x;x = y;y = t; } template<class T> inline T MMAX(T x,T y,T z) {return TMAX(TMAX(x,y),z); }// code begin #define MAXN 5010struct node {int s;int e;int number; }; node tm[MAXN];vector<int> G[MAXN]; vector<int> NG[MAXN]; vector<int> tp; int in[MAXN]; int col[MAXN]; int link[MAXN];int scc; int cnt; int used[MAXN]; int stk1[MAXN],top1; int stk2[MAXN],top2; int isin[MAXN]; int dfn[MAXN]; int low[MAXN]; int id[MAXN]; int N;void gabow_scc(int i) {used[i] = true;stk1[top1++] = i;stk2[top2++] = i;dfn[i] = cnt++;isin[i] = true;FORj( 0,G[i].size(),1 ){if(!used[ G[i][j] ]){gabow_scc(G[i][j]);}else if(isin[G[i][j]]){while(dfn[stk2[top2-1]]>dfn[G[i][j]])top2--;}}if(i==stk2[top2-1]){top2--;int w;do{w = stk1[--top1];isin[w] = false;id[w] = scc;}while(w!=i);scc++;} }void tarjan_scc(int i) {used[i] = true;stk1[top1++] = i;dfn[i] = cnt;low[i] = cnt;cnt++;isin[i] = true;FORj(0,G[i].size(),1){if(!used[ G[i][j] ]){tarjan_scc(G[i][j]);low[i] = TMIN(low[i],low[G[i][j]]);}else if(isin[G[i][j]]){low[i] = TMIN(low[i],dfn[G[i][j]]);}}if(dfn[i]==low[i]){int w;do{w=stk1[--top1];isin[w] = false;id[w] = scc;}while(w!=i);scc++;} }bool Isok(int a,int b) {int sa = tm[a].s;int sb = tm[b].s;int ea = tm[a].e;int eb = tm[b].e;if( sa<eb&&sa>=sb ) return true;if( ea<=eb && ea>sb ) return true;if( sb<ea&&sb>=sa ) return true;if( eb<=ea && eb>sa ) return true;return false; }void dfs(int i) {FORj(0,NG[i].size(),1){if(!col[NG[i][j]]){col[NG[i][j]] = 2;dfs(NG[i][j]);}} }int main() {read;write;int sh,sm,eh,em,po;while(scanf("%d",&N)!=-1){int j=0;FORi(0,N,1){scanf("%d:%d %d:%d %d",&sh,&sm,&eh,&em,&po);tm[j].s = sh*60+sm;tm[j].e = tm[j].s+po;tm[j].number = i;j++;tm[j].e = eh*60+em;tm[j].s = tm[j].e-po;tm[j].number = i;j++;}/*FORi(0,2*N,1){printf("%02d:%02d %02d:%02d\n",tm[i].sh,tm[i].sm,tm[i].eh,tm[i].em);}printf("\n");*///建圖FORi(0,4*N,1){G[i].clear();}//判斷時(shí)間區(qū)間的限制性條件FORi(0,2*N,2){FORj(i+2,2*N,1){// i ,jif( Isok(i,j) ){//printf("相交");//printf(" %02d:%02d %02d:%02d",tm[i].sh,tm[i].sm,tm[i].eh,tm[i].em);//printf(" %02d:%02d %02d:%02d\n",tm[j].sh,tm[j].sm,tm[j].eh,tm[j].em);G[2*i+1].push_back(2*j+0);G[2*j+1].push_back(2*i+0);}}FORj(i+2,2*N,1){// i ,jif( Isok(i+1,j) ){//printf("相交");//printf(" %02d:%02d %02d:%02d",tm[i].sh,tm[i].sm,tm[i].eh,tm[i].em);//printf(" %02d:%02d %02d:%02d\n",tm[j].sh,tm[j].sm,tm[j].eh,tm[j].em);G[2*(i+1)+1].push_back(2*j+0);G[2*j+1].push_back(2*(i+1)+0);}}}FORi(0,2*N,2){//i i+1 G[2*i].push_back(2*(i+1)+1);G[2*(i+1)+1].push_back(2*i);G[2*i+1].push_back(2*(i+1));G[2*(i+1)].push_back(2*i+1);}// sccmemset(used,0,sizeof(used));memset(id,0,sizeof(id));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(isin,0,sizeof(isin));top1 = 0;scc = 1;cnt = 1;FORi(0,4*N,1){if(!used[i]){tarjan_scc(i);}}// 判斷bool f= true;FORi(0,2*N,1){if(id[2*i]==id[2*i+1]){f=false;break;}}if(f){//找一組解printf("YES\n");FORi(1,scc,1){NG[i].clear();}//縮圖memset(link,0,sizeof(link));FORi(0,4*N,1){FORj(0,G[i].size(),1){if( id[i]!=id[G[i][j]] ){NG[id[G[i][j]]].push_back(id[i]);}}}//對(duì)立面FORi(0,2*N,1){link[ id[2*i] ] = id[2*i+1];link[ id[2*i+1] ] = id[2*i];}//取出重復(fù)memset(in,0,sizeof(in));FORi(1,scc,1){vector<int> tmp = NG[i];NG[i].clear();if(tmp.size()>0){sort(tmp.begin(),tmp.end());NG[i].push_back(tmp[0]);in[tmp[0]]++;FORj(1,tmp.size(),1){if(tmp[j]!=tmp[j-1]){NG[i].push_back(tmp[j]);in[tmp[j]]++;}}}}//新圖NGtp.clear();queue<int> qi;FORi(1,scc,1){if(in[i]==0)qi.push(i);}while(!qi.empty()){int cur = qi.front();qi.pop();tp.push_back(cur);FORi(0,NG[cur].size(),1){in[ NG[cur][i] ]--;if( in[ NG[cur][i] ]==0 ){qi.push( NG[cur][i] );}}}// 根據(jù)拓?fù)湫?#xff0c;找解memset(col,0,sizeof(col));//printf("shang\n");//printf("tp.size:%d scc:%d\n",tp.size(),scc);FORi(0,tp.size(),1){if(!col[tp[i]]){col[tp[i]] = 1;//col[link[tp[i]]] = 2;//dfs(link[tp[i]]);}}FORi(0,2*N,2){//printf("col %d: %d %d %02d:%02d %02d:%02d\n",i,col[id[2*i+0]],col[id[2*i+1]],tm[i].s/60,tm[i].s%60,tm[i].e/60,tm[i].e%60);//printf("col %d: %d %d %02d:%02d %02d:%02d\n",i+1,col[id[2*(i+1)+0]],col[id[2*(i+1)+1]],tm[i+1].s/60,tm[i+1].s%60,tm[i+1].e/60,tm[i+1].e%60);//printf("col:%d %d\n",col[id[2*i+1]],col[id[2*0+1]]);if( col[id[2*i+1]]==1 ) //col[id[2*0+1]] printf("%02d:%02d %02d:%02d\n",tm[i].s/60,tm[i].s%60,tm[i].e/60,tm[i].e%60);//printf("col:%d %d\n",col[id[2*(i+1)+1]],col[id[2*0+1]]);if( col[id[2*(i+1)+1]]==1 )printf("%02d:%02d %02d:%02d\n",tm[i+1].s/60,tm[i+1].s%60,tm[i+1].e/60,tm[i+1].e%60);}}else printf("NO\n");//printf("\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ac2012/archive/2011/03/01/1968384.html

總結(jié)

以上是生活随笔為你收集整理的3683的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。