【Ybt OJ】[图论 第4章] 强连通分量 [后半章]

「 「 「图论 」 」 」第 4 4 4章 强连通分量 ( ( (后 2 2 2题 ) ) )

目录：

C.最大半联通子图
D.恒星的亮度
           

C . C. C. 例题 3 3 3 最大半联通子图

洛谷 l i n k link link

分析：

因为存在环 我们先 t a r j a n tarjan tarjan缩点

缩完点后 图就会变成一张 D A G DAG DAG 并且缩完点后是逆拓扑序

然后就要求出最长链的大小和个数

t a r j a n tarjan tarjan完会有一些重边 所以在 D A G DAG DAG上 d p dp dp时要先去重

然后就是正常统计了

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
#include<bitset>
//#pragma GCC optimize(2)
#define reg register
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int N=1e5+5,M=2e6+5;
int n,m,tot,mod,Index,size,tot2,head[N],low[N],dnf[N],stack[N],len[N],con[N],top;
bool f[N];
int head2[N],used[N],val[N],v[N];
struct node{
	int to,next;
}a[M];
struct node2{
	int to,next;
}topo[M];
void add(int x,int y){
	a[++tot]=(node){y,head[x]};
	head[x]=tot;
}
void Add(int x,int y){
	topo[++tot2]=(node2){y,head2[x]};
	head2[x]=tot2;
}
void tarjan(int x){
	dnf[x]=low[x]=++Index;
	stack[++top]=x;
	f[x]=1;
	for(int i=head[x];i;i=a[i].next)
	{
		int qwq=a[i].to;
		if(!dnf[qwq]){
			tarjan(qwq);
			low[x]=min(low[x],low[qwq]);
		}else if(f[qwq]) low[x]=min(low[x],dnf[qwq]);
	}
	if(dnf[x]==low[x])
	{
		size++;
		int qwq=-1;
		while(qwq!=x)
		{
			qwq=stack[top--];
			con[qwq]=size;
			len[size]++;
			f[qwq]=0;
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&mod);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
		if(!dnf[i]) tarjan(i);
	for(int j=1;j<=n;j++)
	{
		val[j]=len[j];
		v[j]=1;
		for(int i=head[j];i;i=a[i].next)
		{
			int qwq=a[i].to;
			if(con[j]==con[qwq]) continue;
			Add(con[j],con[qwq]);
		}
	}
	for(int x=size;x>=1;x--)  //逆拓扑序
	{
		for(int i=head2[x];i;i=topo[i].next)
		{
			int qwq=topo[i].to;
			if(used[qwq]==x) continue;  //去重边
			used[qwq]=x;
			if(val[qwq]<val[x]+len[qwq])
			{
				val[qwq]=val[x]+len[qwq];  //大小
				v[qwq]=v[x];
			}else if(val[qwq]==val[x]+len[qwq])
			{
				v[qwq]+=v[x];  //个数
				v[qwq]%=mod;
			}
		}
	}
	int ans=0,cnt=0;
	for(int i=1;i<=size;i++)
	{
		if(val[i]>ans)
		{
			ans=val[i];
			cnt=v[i];
		}else if(val[i]==ans)
		{
			cnt+=v[i];
			cnt%=mod;
		}
	}
	printf("%d\n%d",ans,cnt);
	
	return 0;
}
           

D . D. D. 例题 4 4 4 恒星的亮度

洛谷 l i n k link link

分析：

把 A A A不小于 B B B 和 A A A不大于 B B B 转换 变成 A A A大于等于 B B B 和 A A A小于等于 B B B

那如果 A < B A<B A<B 那么 B B B可以为 A + 1 A+1 A+1 如果有等于 那就 B = A B=A B=A就行了

B < A B<A B<A 和 B B B小于等于 A A A 的关系同理

然后 就会发现有环 那就要 t a r j a n tarjan tarjan缩点

把 A < B A<B A<B或 A < = B A<=B A<=B 连一条 A A A到 B B B的有向边

然后缩点缩在一起 就是亮度相同 ( B (B (B的关系也一样 ) ) )

但一个环中如果有小于 那就会有矛盾 因为你又要求亮度相同 但这条边却是小于

那就要把边分类 成可以参与缩点 和不可以参与的

如果不能参与缩点的参与了缩点 那就无解了

然后就在拓扑序列里 d p dp dp 转移的时候 判断下边的类型 小于就是原来的边 + 1 +1 +1 其他就是原来的

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
#include<bitset>
#define Ctnue continue
//#pragma GCC optimize(2)
#define reg register
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int N=1e5+5;
struct node{
	int to,next,kd;
}a[N*5],b[N*5];
int head[N],Q,con[N],n,m,Kd,x,y,Index,top,head2[N];
int dnf[N],low[N],tot,in[N],tmp,Q2,stack[N],val[N],dis[N];
queue<int> q; 
void add(int x,int y,int k)
{
	a[++Q]=(node){y,head[x],k};
	head[x]=Q;
}
void Add(int x,int y,int k)
{
	b[++Q2]=(node){y,head2[x],k};
	head2[x]=Q2;
}
void tarjan(int x)
{
	stack[++top]=x;
	dnf[x]=low[x]=++Index;
	for(int i=head[x];i;i=a[i].next)
	{
		int qwq=a[i].to;
		if(!dnf[qwq])
		{
			tarjan(qwq);
			low[x]=min(low[x],low[qwq]);
		}
		else if(!con[qwq]) low[x]=min(low[x],low[qwq]);
	}
	if(dnf[x]==low[x])
	{
		con[x]=++tot;
		val[tot]=1;
		while(stack[top]!=x)
		{
			val[tot]++;
			con[stack[top--]]=tot;
		}
		top--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&Kd,&x,&y);
		if(Kd==1){
			add(x,y,0);
			add(y,x,0);
			Ctnue;
		}
		else if(Kd==2){add(x,y,1);Ctnue;}  //分类连边
		else if(Kd==3){add(y,x,0);Ctnue;}
		else if(Kd==4){add(y,x,1);Ctnue;}
		else if(Kd==5){add(x,y,0);Ctnue;}
	}
	for(int i=1;i<=n;i++)
		if(!dnf[i]) tarjan(i);
	ll ans=0;
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=a[j].next)
		{
			int qwq=a[j].to;
			if(con[i]!=con[qwq])  //不同点之间的边
			{
				Add(con[i],con[qwq],a[j].kd);
				in[con[qwq]]++;  //统计入度
			}else if(a[j].kd==1){  //无解了
				puts("-1");
				return 0;
			}
		}
	for(int i=1;i<=tot;i++)
		if(!in[i]){
			q.push(i);
			dis[i]=1;
		}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		ans+=(long long)(dis[x]*val[x]);  //统计进总亮度 要乘包含点的个数
		for(int i=head2[x];i;i=b[i].next)
		{
			int qwq=b[i].to;
			in[qwq]--;
			dis[qwq]=max(dis[qwq],dis[x]+b[i].kd);  //看边类型是+1还是原来的
			if(!in[qwq]) q.push(qwq);
		}
	}
	printf("%lld",ans);
	
	return 0;
}