图论--2-SAT--HDOJ/HDU 1824 Let's go home

Problem Description

小时候，乡愁是一枚小小的邮票，我在这头，母亲在那头。

—— 余光中

集训是辛苦的，道路是坎坷的，休息还是必须的。经过一段时间的训练，lcy决定让大家回家放松一下，但是训练还是得照常进行，lcy想出了如下回家规定，每一个队（三人一队）或者队长留下或者其余两名队员同时留下；每一对队员，如果队员A留下，则队员B必须回家休息下，或者B留下，A回家。由于今年集训队人数突破往年同期最高记录，管理难度相当大，lcy也不知道自己的决定是否可行，所以这个难题就交给你了，呵呵，好处嘛~，免费**漂流一日。

Input

第一行有两个整数，T和M，1<=T<=1000表示队伍数，1<=M<=5000表示对数。

接下来有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

（1）题目第一个条件：每一个队或者队长留下或者其与两名队员同时留下，或者表明只能为两种情况中的一种；假设三人为A,B,C，队长为A，0表示不留下，1表示留下，因为B与C同时留下或者不留下，只要B，C中其中一个没有留下或者留下，则B,C中另一个也同样留下或者不留下，所以可以从该条件中推导出六条等价关系，即A不留下->B，C同时留下，A留下->B，C同时不留下，B留下->C留下，A不留下，B留下->C留下，A不留下，C留下->B留下，A不留西，C不留下->B不留下，A留下；

（2）题目中第二个条件：每一对队员，如果队员A留下，则B必须回家休息，或者B留下，A必须回家休息；则可以推导出两条等价式：A留下->B不留下，B留下->A不留下，注意在这个条件中可以A，B都不留下；

AC代码：

#include <cstdio>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <algorithm>

#include <iostream>

#define MAXN 7000+10

#define MAXM 400000

#define INF 1000000

using namespace std;

vector<int> G[MAXN];

int low[MAXN], dfn[MAXN];

int dfs_clock;

int sccno[MAXN], scc_cnt;

stack<int> S;

bool Instack[MAXN];

int N, M;

void init()

{

	for(int i = 0; i <=6*N; i++) G[i].clear();

	while(S.size()) S.pop();

	dfs_clock=scc_cnt=0;

}

void getMap()

{

    int a,b,c;

	for(int i=0;i<N;i++)

    {

       scanf("%d %d %d",&a,&b,&c);

        G[a+N*3].push_back(b);

        G[a+N*3].push_back(c);

        G[b+3*N].push_back(a);

        G[c+3*N].push_back(a);

    }

    while(M--)

    {

        scanf("%d%d",&a,&b);

        G[a].push_back(b+N*3);

        G[b].push_back(a+N*3);

    }

}

void tarjan(int u, int fa)

{

	int v;

	low[u] = dfn[u] = ++dfs_clock;

	S.push(u);

	Instack[u] = true;

	for(int i = 0; i < G[u].size(); i++)

	{

		v = G[u][i];

		if(!dfn[v])

		{

			tarjan(v, u);

			low[u] = min(low[u], low[v]);

		}

		else if(Instack[v])

		low[u] = min(low[u], dfn[v]);

	}

	if(low[u] == dfn[u])

	{

		scc_cnt++;

		for(;;)

		{

			v = S.top(); S.pop();

			Instack[v] = false;

			sccno[v] = scc_cnt;

			if(v == u) break;

		}

	}

}

void find_cut(int l, int r)

{

	memset(low, 0, sizeof(low));

	memset(dfn, 0, sizeof(dfn));

	memset(sccno, 0, sizeof(sccno));

	memset(Instack, false, sizeof(Instack));

	dfs_clock = scc_cnt = 0;

	for(int i = l; i <= r; i++)

	if(!dfn[i]) tarjan(i, -1);

}

void solve()

{

    for(int i = 0; i < 3*N; i++)

    {

        if(sccno[i] == sccno[i+3*N])//矛盾

        {

            printf("no\n");

            return ;

        }

    }

    printf("yes\n");

}

int main()

{

	while(scanf("%d%d", &N, &M) != EOF)

	{

		init();

		getMap();

		find_cut(0, 6*N-1);

		solve();

	}

	return 0;

}

巴特西

图论--2-SAT--HDOJ/HDU 1824 Let's go home

最新文章

热门文章