【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;
}