首页 > 搜索 > DFS搜索 > HDU 3062-Party-DFS-[解题报告]HOJ
2014
03-01

HDU 3062-Party-DFS-[解题报告]HOJ

Party

问题描述 :

有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席?

输入:

n: 表示有n对夫妻被邀请 (n<= 1000)
m: 表示有m 对矛盾关系 ( m < (n – 1) * (n -1))

在接下来的m行中,每行会有4个数字,分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ,0表示妻子 ,1是丈夫
夫妻编号从 0 到 n -1

输出:

n: 表示有n对夫妻被邀请 (n<= 1000)
m: 表示有m 对矛盾关系 ( m < (n – 1) * (n -1))

在接下来的m行中,每行会有4个数字,分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ,0表示妻子 ,1是丈夫
夫妻编号从 0 到 n -1

样例输入:

2 
1
0 1 1 1 

样例输出:

YES

简单2-SAT问题,看了一下网上的资料, 强连通分量的更深层次的应用,

目前只知道这样求,具体算法的原理还有点模糊,下去应该好好看看,,,




#include<stdio.h>
#include<string.h>
#include<stack>
#define N 2010
using namespace std;
int n,m,low[N],dfs[N],belong[N],ins[N],idx,ans;
struct Eage
{
	int ed;
	Eage *next;
}*eage[N];
void addeage(int x,int y)
{
	Eage *p=new Eage;
	p->ed=y;
	p->next=eage[x];
	eage[x]=p;
}
stack<int>Q;
void Tarjan(int x)  
{  
    int v;  
    low[x]=dfs[x]=idx++;  
    Q.push(x);  
    ins[x]=1;  
    for(Eage *p=eage[x];p;p=p->next)  
    {  
        if(dfs[p->ed]==-1)  
        {  
            Tarjan(p->ed);  
            low[x]=low[x]>low[p->ed]?low[p->ed]:low[x];  
        }  
        else if(ins[p->ed]==1)  
            low[x]=low[x]>dfs[p->ed]?dfs[p->ed]:low[x];  
    }  
    if(dfs[x]==low[x])  
    {  
          
        while(1)  
        {  
            v=Q.top();  
            Q.pop();  
            belong[v]=ans;  
            ins[v]=0;
            if(v==x)break;  
        }  
        ans++;    
    }  
}  
int main()
{
	int i,x,y,a,b,p,q;
	while(scanf("%d",&n)!=-1)
	{
		memset(eage,NULL,sizeof(eage));
		memset(dfs,-1,sizeof(dfs));
		memset(ins,0,sizeof(ins));
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d%d",&x,&y,&a,&b);
			x=x*2+a;
			y=y*2+b;
			if(a==0)
			p=x+1;
			else p=x-1;
			if(b==0)
				q=y+1;
			else q=y-1;
			addeage(x,q);
			addeage(y,p);
		}
		idx=ans=0;
		for(i=0;i<2*n;i++)
		{
			if(dfs[i]==-1)
				Tarjan(i);
		}
		for(i=0;i<n;i++)
		{
			a=i*2;
			b=i*2+1;
			if(belong[a]==belong[b])
				break;
		}
		if(i==n)
			printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}








参考:http://blog.csdn.net/aixiaoling1314/article/details/9346663


,
  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。