最大半连通子图

题目链接： / /

题目大意

我们称一个子图是半连通子图，就是这个子图的任意两个点之间都有路径从一个点到另一个点。（只要能从任意一边到另一边即可）

问你一个图的最大半连通子图是多大，这样的图有多少个，个数对一个给出的数取模。

思路

那你可以想象一下，对于一个联通分块，它里面的点集合选一个子集连上边，它都是最大半连通子图。

那还有怎样会构成呢？

你会想到，对于一条链，它也是半连通的。

那你会想到缩点之后，图就变成了 DAG，那你找一条路径最大的链就可以了。

当然，不是所有点的权值都是一，因为你缩点了，那权值就是包含原来点的数量。

然后你就得到最长的长度，然后你要看有多少条。

那你再 dfs 跑一次，想最短路的找路径一样弄。

其实求的这个部分好像可以按拓扑序 dp 来搞。

但是我写完看题解才发现的，反正我的也行（类似记忆化一下），就不管了。

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct node {
   	int to, nxt;}e[1000001], e_n[1000001];struct road {
   	int x, y;}a[1000001];int n, m, mo, le[100001], KK;int dfn[100001], low[100001];int in[100001], tmp, n_n;int st[100001], num[100001];int le_n[100001], KK_n;int dis[100001], answer, temp;long long answer_num, rem_num[100001];bool cmp(road x, road y) {
   //用来去重边的排序	if (x.x != y.x) return x.x < y.x;	return x.y < y.y;}void add(int x, int y) {
   //原来的图	e[++KK] = (node){
   y, le[x]}; le[x] = KK;}void add_n(int x, int y) {
   //缩点后的图	e_n[++KK_n] = (node){
   y, le_n[x]}; le_n[x] = KK_n;}void tarjan(int now) {
   //tarjan缩点	dfn[now] = low[now] = ++tmp;	st[++st[0]] = now;		for (int i = le[now]; i; i = e[i].nxt)		if (!dfn[e[i].to]) {
   			tarjan(e[i].to);			low[now] = min(low[now], low[e[i].to]);		}		else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);		if (dfn[now] == low[now]) {
   		in[now] = ++n_n;		num[n_n] = 1;		while (st[st[0]] != now) {
   			num[n_n]++;			in[st[st[0]]] = n_n;			st[0]--;		}		st[0]--;	}		return ;}long long dfs(int now) {
   //dfs跑出最长路径	if (dis[now]) return dis[now];		int re = num[now];	for (int i = le_n[now]; i; i = e_n[i].nxt) {
   		dis[e_n[i].to] = dfs(e_n[i].to);		re = max(re, num[now] + dis[e_n[i].to]);	}		return re;}int get_num(int now, int still) {
   //再跑一次找个数	if (!still) return 1;	if (rem_num[now] != -1) return rem_num[now];		rem_num[now] = 0;	for (int i = le_n[now]; i; i = e_n[i].nxt) {
   		if (dis[e_n[i].to] + num[now] == dis[now]) {
   			rem_num[now] += get_num(e_n[i].to, still - num[e_n[i].to]);			rem_num[now] %= mo;		}	}		return rem_num[now];}int main() {
   	scanf("%d %d %d", &n, &m, &mo);	for (int i = 1; i <= m; i++) {
   		scanf("%d %d", &a[1].x, &a[1].y);		add(a[1].x, a[1].y);	}		for (int i = 1; i <= n; i++)//缩点		if (!dfn[i]) tarjan(i);		for (int i = 1; i <= n; i++)//缩点之后的图要去重边		for (int j = le[i]; j; j = e[j].nxt)			if (in[i] != in[e[j].to]) {
   				temp++;				a[temp].x = in[i];				a[temp].y = in[e[j].to];			}		sort(a + 1, a + temp + 1, cmp);	if (temp >= 1) add_n(a[1].x, a[1].y);	for (int i = 2; i <= temp; i++)		if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)			add_n(a[i].x, a[i].y);		for (int i = 1; i <= n_n; i++)//先跑最长路径		if (!dis[i]) {
   			dis[i] = dfs(i);			answer = max(answer, dis[i]);		}		printf("%d\n", answer);		memset(rem_num, -1, sizeof(rem_num));		for (int i = 1; i <= n_n; i++)//再跑个数		if (dis[i] == answer) {
   			rem_num[i] = get_num(i, answer - num[i]);			answer_num += (1ll * rem_num[i]) % mo;			answer_num %= mo;		}		printf("%lld", answer_num);		return 0;}

转载地址：http://vavh.baihongyu.com/

你可能感兴趣的文章