Graph_Master(连通分量_Poj

Poj_1904

背景：本来是在做Voj的连通分量，做到了E（ hdu_4685 ），想到了二分图，但是笔者只会最大匹配，但题目要求要输出所有的最大匹配情况，想了好久都没想出来怎么做，因为如果我已知一个最大匹配，那么就可以将公主连反向边指向王子，然后跑tarjan，将每个强连通分量的王子配公主输出即可，但是这题没有给出最大匹配，这个还不是最坑的，因为可以跑一次最大匹配，最坑的是n个王子，但是有m个公主，看到这个真的想打人，这个就真的难受了，因为如果有人单身怎么办？？所以就去百度了，然后题解几乎全部提及Poj1904，于是乎笔者就去找到了这题，这题就是笔者想的那个给出匹配的版本，所以很快A掉了，但是！！re了4发，因为王子公主就2000，笔者边集数组没有多想，只开了两倍，到最后一直开到10w都还是re，最后百度一看，20W起加（貌似有个204000）过的，最后数组开到26w就过去了，不得不说这题的这个坑点真的是，很难过了。

题目大意：给出n个王子和他们仰慕的公主，接下来给出每个公主已经匹配的王子（即给出一组最大匹配），输出每个王子最多能和哪些公主匹配。

题解：对于王子仰慕的公主建边，而题目提供的最大匹配，用于建反向边，然后tarjan缩点，同一个分量里面的王子公主随意输出（笔者排了个序方便差错，忘了题目是否有要求）。

PS：今天应该可以把hdu_4685写出来，题解说是要虚拟出公主和王子，容笔者仔细想想，感觉想通了实现应该很快，毕竟这些点都挺熟悉的。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

const int N = 5005;

const int M = 260000;

const int INF = 0x3f3f3f3f;

struct Edge

{

	int u, v, nxt;

};

Edge edge[M];

int ecnt, head[N];

int top, sum, dep;

bool vis[N];

int sta[N], low[N], dfn[N], col[N];

int ans[N];

void _add( int a, int b )

{

	edge[ecnt].u = a;

	edge[ecnt].v = b;

	edge[ecnt].nxt = head[a];

	head[a] = ecnt ++;

}

void tarjan( int u )

{

	sta[++top] = u;

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

	vis[u] = 1;

	for ( int i = head[u]; i+1; i = edge[i].nxt )

	{

		int v = edge[i].v;

		if ( !dfn[v] )

		{

			tarjan(v);

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

		}

		else if ( vis[v] )

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

	}

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

	{

		vis[u] = 0;

		col[u] = ++sum;

		while ( sta[top] != u )

		{

			vis[sta[top]] = 0;

			col[sta[top--]] = sum;

		}

		top --;

	}

}

int main()

{

	int n;

	scanf("%d", &n);

	memset(head,-1,sizeof(head));

	for ( int i = 1; i <= n; i ++ )

	{

		int cn, pricn;

		scanf("%d", &cn);

		while ( cn -- )

		{

			scanf("%d", &pricn);

			_add( i, pricn + n );

		}

	}

	for ( int i = 1; i <= n; i ++ )

	{

		int pric;

		scanf("%d", &pric);

		_add( pric + n, i );

	}

	for ( int i = 1; i <= n; i ++ )

		if ( !dfn[i] )

			tarjan(i);

	for ( int i = 1; i <= n; i ++ )

	{

		int cnt = 0;

		for ( int j = head[i]; j+1; j = edge[j].nxt )

		{

			int v = edge[j].v;

			if ( col[i] == col[v] )

				ans[cnt++] = v - n;

		}

		sort(ans,ans+cnt);

		printf("%d", cnt);

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

			printf(" %d", ans[i]);

		printf("\n");

	}

	return 0;

}

巴特西

Graph_Master(连通分量_Poj_1904)

最新文章

热门文章