Poj 3683 Priest John's Busiest Day (2-SAT+拓扑排序输出方案)

灰太狼 2022-08-11 00:43 18阅读 0赞

题意：有个小镇上有n对夫妻要举办婚礼，每队夫妻都要请镇上的牧师举行一个仪式，但是镇上只有一个牧师，牧师一次只能为一对夫妻做仪式。

已知每队夫妻的婚礼的起始t1和结束的时间t2， 他们举办仪式的时间是d，仪式只能在婚礼开始的前d时间举行或者在结束之前的d内举行。问牧师能不能合理安排，使得每对夫妻都能举办仪式？

思路：对于每一对夫妻，他们要么在开始时做仪式，要么在结束时做仪式，所以是2-SAT模型。

这题要输出任一个方案。

#include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    #define WHITE -1  
    #define RED 1  
    #define BLUE 0
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int MAXN = 1010;  
    const int VN   = MAXN*2;  
    const int EN   = VN*VN*2; 
    int n,m;
    
    struct Couple{  
    	int  d;  
    	int  t1, t2;  
    }data[MAXN]; 
    
    struct Edge{
    	int u,v,next;
    };
    
    void time_out(int t, int d){  
        printf("%02d:%02d %02d:%02d\n", t/60, t%60, (t+d)/60, (t+d)%60);  
    }
    
    class Graph{
    public:
    	int head[VN],size;
    	Edge E[EN];
    	void init(){
    		size = 0;
    		memset(head, -1, sizeof(head));
    	}
    	void Add (int u,int v){
    		E[size].u = u;
    		E[size].v = v;
    		E[size].next = head[u];
    		head[u] = size++;
    	}
    }g,g2; //g为原图,g2为新图
    
    class Two_Sat{
    public:
    	bool Check (const Graph&g, const int n){
    		SCC(g,n);
    		for (int i=0;i<n;i++)
    			if (belong[i*2] == belong[i*2+1])
    				return false;
    		return true;
    	}
    	
    	void toposort (const Graph&g, Graph& g1, const int n) {
    		g1.init();  
    		memset(indeg, 0, sizeof(indeg));
    		int i;
    		for (i=0;i<n;i++)
    		{
    			opp[belong[i*2]] = belong[i*2+1];
    			opp[belong[i*2+1]] = belong[i*2];
    		}
    		for (int e=0;e<g.size;e++)
    		{
    			int u = belong[g.E[e].u];
    			int v = belong[g.E[e].v];
    			if (u == v) continue;
    			indeg[u]++;
    			g1.Add(v,u);
    		}
    		
    		queue<int>que;  
    		memset(color, WHITE, sizeof(color));  
    		for (i=1;i<=bcnt;i++)
    			if (!indeg[i])
    				que.push(i);
    
    		int* head = g1.head;
    		Edge* E   = g1.E;
    		
    		while (!que.empty())
    		{
    			int u = que.front();
    			que.pop();
    			if (color[u] != WHITE) continue;
    			color[u] = RED;
    			color[opp[u]] = BLUE;
    
    			for (int e=head[u]; e!=-1; e=E[e].next)
    			{
    				int v = E[e].v;
    				if (--indeg[v] == 0)
    					que.push(v);
    			}
    		}
    
    		for (i=0;i<n;i++)
    			if (color[belong[i*2]]==RED)  //!!注意*2
    				time_out(data[i].t1, data[i].d);
    			else
    				time_out(data[i].t2-data[i].d, data[i].d);
    	}
    
    private:
    	int top, bcnt, idx;
    	int sta[VN],belong[VN];
    	int dfn[VN],low[VN];
    	bool inStack[VN];
    
    	// 求方案  
    	int indeg[VN];
    	int color[VN];
    	int opp[VN];
    	
    	void targan (const Graph&g, const int u){
    		int v;
    		dfn[u] = low[u] = ++idx;
    		sta[top++] = u;
    		inStack[u] = true;
    		
    		for (int i=g.head[u]; i!=-1; i=g.E[i].next){
    			v = g.E[i].v;
    			if (dfn[v] < 0){
    				targan(g, v);
    				low[u] = min(low[u], low[v]);
    			}
    			else if(inStack[v])
    				low[u] = min(low[u], dfn[v]);
    		}
    		
    		if (dfn[u] == low[u]){
    			++bcnt;
    			do{
    				v = sta[--top];
    				inStack[v] = false;
    				belong[v] = bcnt;
    			}while(u != v);
    		}
    	}
    
    	void SCC (const Graph&g, int n){
    		top=bcnt=idx=0;
    		memset(dfn,-1,sizeof(dfn));
    		memset(low,0,sizeof(low));
    		memset(belong,0,sizeof(belong));
    		memset(inStack,false,sizeof(inStack));
    		for (int i=0; i<2*n;i++)
    			if (dfn[i] < 0) targan(g,i);
    	}
    }sat;
    
    bool isCross(int a1, int b1, int a2, int b2){
    	return !(a2>=b1 || a1>=b2);
    }
      
    int main ()
    {
    	while (~scanf("%d", &n))
    	{
    		int a,b,i;
    		g.init(); 
    		for (i=0;i<n;i++)
    		{
    			scanf("%d:%d",&a,&b);
    			data[i].t1 = a*60+b;
    			scanf("%d:%d",&a,&b);
    			data[i].t2 = a*60+b;
    			scanf("%d",&data[i].d);
    		}
    		for (i=0;i<n;i++)
    			for (int j=i+1;j<n;j++)
    			{
    				const Couple& a=data[i];
    				const Couple& b=data[j];
    				int u=i*2,v=j*2;
    				if (isCross(a.t1, a.t1+a.d, b.t1, b.t1+b.d))
    					g.Add(u,v^1),g.Add(v,u^1); 
    				if (isCross(a.t1, a.t1+a.d, b.t2-b.d, b.t2)) //
    					g.Add(u,v),g.Add(v^1,u^1);
    				if (isCross(a.t2-a.d, a.t2, b.t1, b.t1+b.d))
    					g.Add(u^1,v^1),g.Add(v,u);
    				if (isCross(a.t2-a.d, a.t2, b.t2-b.d, b.t2))
    					g.Add(u^1,v),g.Add(v^1,u);
    			}    
    		if (sat.Check(g, n))
    		{
                puts("YES");  
                sat.toposort(g,g2,n);  
            }
    		else puts("NO");
    	}
    	return 0;
    }
    
    /*
    2
    08:00 09:00 30
    08:15 09:00 20
    
    2
    08:00 09:00 30
    08:00 09:00 30
    
    3
    08:00 09:00 20
    08:20 09:00 20
    08:40 09:00 20
    
    ans:
    YES
    08:00 08:30
    08:40 09:00
    
    YES
    08:00 08:30
    08:30 09:00
    
    YES
    08:00 08:20
    08:20 08:40
    08:40 09:00
    
    
    3
    08:00 09:00 30
    08:15 09:00 20
    08:30 08:50 1
    YES
    08:00 08:30
    08:40 09:00
    08:30 08:31
    3
    08:00 09:00 30
    08:15 09:00 10
    08:30 08:50 10
    YES
    08:00 08:30
    08:50 09:00
    08:30 08:40
    4
    08:00 09:00 30
    08:15 09:00 10
    08:30 08:50 10
    08:00 10:00 60
    YES
    08:00 08:30
    08:50 09:00
    08:30 08:40
    09:00 10:00
    6
    08:00 09:00 30
    08:15 09:00 10
    08:30 08:50 10
    08:00 10:00 20
    09:00 09:20 10
    09:00 09:40 20
    YES
    08:00 08:30
    08:50 09:00
    08:30 08:40
    09:40 10:00
    09:00 09:10
    09:20 09:40
    5
    08:00 09:00 30
    08:15 09:00 10
    08:30 08:50 10
    08:00 10:00 20
    09:00 09:20 10
    YES
    08:00 08:30
    08:50 09:00
    08:30 08:40
    09:40 10:00
    09:00 09:10
    9
    08:00 09:00 30
    08:15 09:00 10
    08:30 08:50 10
    08:00 10:00 20
    09:00 09:20 10
    09:00 09:40 20
    10:00 10:30 10
    10:20 10:30 10
    10:10 10:20 10
    YES
    08:00 08:30
    08:50 09:00
    08:30 08:40
    09:40 10:00
    09:00 09:10
    09:20 09:40
    10:00 10:10
    10:20 10:30
    10:10 10:20
    */