牛子图论1(二分图+连通性)

发布于：2025-09-04 ⋅ 阅读:(25) ⋅ 点赞:(0)

二分图及最大匹配

NC20483 假期的宿舍

题意

学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。
而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。
问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

思路

即将点分为所有需要床的学生和床，看最大匹配是否等于所有需要床的学生数即可

  • 对于本校住校生，其需要床，并且可以匹配认识的本校住校生的床和自己的床
  • 对于外校生，其可以匹配认识的本校住校生的床

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=100;
vector<int>e[N];


void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++) e[i].clear();
	vector<int>school(n+1),home(n+1);
	for(int i=1;i<=n;i++) cin>>school[i];
	for(int i=1;i<=n;i++) cin>>home[i];
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(!school[i]) cnt++;
		else if(!home[i]) cnt++;
	}
	
	vector<vector<int>>a(n+1,vector<int>(n+1));
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>a[i][j];
	}
	
	for(int i=1;i<=n;i++)
	{
		if(school[i] && !home[i]) e[i].pb(i);
		for(int j=1;j<=n;j++)
		{
			if(j==i) continue;
			if(school[i] && !home[i] && a[i][j] && school[j]) e[i].pb(j);
			if(!school[i] && a[i][j] && school[j]) e[i].pb(j);
		}
	}
	
	int ans=0;
	vector<int>link(n+1);
	vector<int>vis(n+1);
	auto dfs=[&](auto && dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			if(!link[ed] || dfs(dfs,link[ed]))
			{
				link[ed]=u;
				return true;
			}
		}
		return false;
	};
	
	for(int i=1;i<=n;i++)
	{
		fill(all(vis),0);
		if(dfs(dfs,i)) ans++;
	}
	if(cnt==ans) cout<<"^_^"<<endl;
	else cout<<"T_T"<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--)
	solve();
	
	return 0;
}

NC 51316

题意

一张平面图上有若干小人和房子，小人和房子的数量相等，小人可以上下左右移动，代价为1金币，求所有小人都有房子的最小代价

思路

每个小人到房子的代价即其的曼哈顿距离，问题转化为小人和房子两两匹配的最小权，我们将边权取反后就变成了二分图最大权完美匹配模板

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=110;
int match[N];
int va[N],vb[N];
ll w[N][N];
ll la[N],lb[N];
ll d[N];

int cnth,cntm;

bool dfs(int x)
{
	va[x]=1;
	for(int y=1;y<=cnth;y++)
	{
		if(!vb[y])
		{
			if(la[x]+lb[y]==w[x][y])
			{
				vb[y]=1;
				if(!match[y] || dfs(match[y]))
				{
					match[y]=x;
					return true;
				}
			}
			else d[y]=min(d[y],la[x]+lb[y]-w[x][y]);
		}
	}
	return false;
}

ll km()
{
	for(int i=1;i<=cnth;i++) la[i]=-INF;
	for(int i=1;i<=cntm;i++)
	{
		for(int j=1;j<=cnth;j++) la[i]=max(la[i],w[i][j]);
	}
	
	for(int i=1;i<=cnth;i++) lb[i]=0;
	
	for(int i=1;i<=cntm;i++)
	{
		while(1)
		{
			fill(va+1,va+1+cntm,0);
			fill(vb+1,vb+1+cnth,0);
			fill(d+1,d+cnth+1,INF);
			if(dfs(i)) break;
			
			ll delta=INF;
			for(int j=1;j<=cnth;j++) if(!vb[j]) delta=min(delta,d[j]);
			
			for(int j=1;j<=cnth;j++)
			{
				if(va[j]) la[j]-=delta;
				if(vb[j]) lb[j]+=delta;
			}
		}
	}
	ll res=0;
	for(int i=1;i<=cnth;i++) res+=w[match[i]][i];
	return res;
}


void solve()
{
	int n,m;
	while(cin>>n>>m,n && m)
	{
		memset(match,0,sizeof match);
		vector<vector<char>>a(n+1,vector<char>(m+1));
		vector<PII>house,human;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
				if(a[i][j]=='H') human.pb({i,j});
				else if(a[i][j]=='m') house.pb({i,j});
			}
		}
		
		cntm=human.size();
		cnth=house.size();
		
		for(int i=1;i<=cntm;i++)
		{
			for(int j=1;j<=cnth;j++) w[i][j]=INF;
		}
		
		for(int i=0;i<cntm;i++)
		{
			for(int j=0;j<cnth;j++)
			{
				auto [x,y]=human[i];
				auto [a,b]=house[j];
				w[i+1][j+1]=-(abs(x-a)+abs(y-b));
			}
		}
		ll ans=km();
		cout<<-ans<<endl;
	
	}
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

POJ3041

题意

给定一个n∗nn*nn∗n的矩阵，以及k个陨石的坐标，每次可以选择击碎一行或一列的陨石，求击碎所有陨石的最小操作次数

思路

如果将每个陨石坐标的行向列连边，那么对于每一个行顶点，每条出边都代表一颗陨石，那么现在问题转化成每次可以选择一个顶点的全部出边，求选择最少顶点覆盖所有边的顶点数，毫无疑问是最小点覆盖问题，最小点覆盖问题又等价于最大边匹配

代码

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=510;
vector<int>e[N];

void solve()
{
	int n,k;
	cin>>n>>k;
	
	for(int i=1;i<=k;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	ll ans=0;
	vector<int>vis(n+1),match(n+1);
	
	auto dfs=[&](auto &&dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			
			if(!match[ed] || dfs(dfs,match[ed]))
			{
				match[ed]=u;
				return true;
			}
		}
		return false;
	};
	
	for(int i=1;i<=n;i++)
	{
		fill(all(vis),0);
		if(dfs(dfs,i)) ans++;
	}
	cout<<ans<<endl;
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

P1129矩阵游戏

题意

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 n×nn \times nn×n 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

  • 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
  • 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

第一行包含一个整数 TTT，表示数据的组数，对于每组数据，输入格式如下：

第一行为一个整数，代表方阵的大小 nnn。
接下来 nnn 行，每行 nnn 个非零即一的整数，代表该方阵。其中 000 表示白色，111 表示黑色。

对于每组数据，输出一行一个字符串，若关卡有解则输出 Yes，否则输出 No。

  • 对于 20%20\%20% 的数据，保证 n≤7n \leq 7n≤7。
  • 对于 50%50\%50% 的数据，保证 n≤50n \leq 50n≤50。
  • 对于 100%100\%100% 的数据，保证 1≤n≤2001 \leq n \leq 2001≤n≤200，1≤T≤201 \leq T \leq 201≤T≤20。

思路

可以发现对于同一行同一列的点，交换之后仍然同行同列，所有问题转化为能否找到n个不同行同列的点(这样一定能转化为主对角线上),考虑对于黑色格子的行向列连边，问题又转化为二分图的最大匹配

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=210;
vector<int>e[N];

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++) e[i].clear();
	vector<vector<int>>a(n+1,vector<int>(n+1));

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]) e[i].pb(j);
		} 
	}
	
	
	
	vector<int>match(n+1),vis(n+1);
	
	auto dfs=[&](auto &&dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			
			if(!match[ed] || dfs(dfs,match[ed]))
			{
				match[ed]=u;
				return true;
			}
			
		}
		return false;
	};
	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		fill(all(vis),0);
		if(dfs(dfs,i)) ans++;
	}
	if(ans==n) yes;
	else no;
	
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--)
	solve();
	
	return 0;
}

NC236758 占领城市

题意

n个点m条道路，选择最少的道路覆盖全部的点，不可以重复经过点

思路

最少不重复路径覆盖板子题,对于互相可达的两个点连一条边，那么每次选择一条边可以覆盖两个城市，答案即为n-最大匹配

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=510;

vector<int>e[N];

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	int ans=0;
	vector<int>vis(n+1),match(n+1);
	
	auto dfs=[&](auto && dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			
			if(!match[ed] || dfs(dfs,match[ed]))
			{
				match[ed]=u;
				return true;
			}
		}
		return false;
	};
	
	for(int i=1;i<=n;i++)
	{
		fill(all(vis),0);
		if(dfs(dfs,i)) ans++;
	}
	cout<<n-ans<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC 236759中心图

题意

给出一个 nnn 个节点， mmm 条边的有向图，你可以进行若干次操作，每次操作可以删除图中的一条边或者添加一条有向边，使得原图变为中心图。

定义一个图是中心图，当且仅当它满足如下条件：

1. 图中没有重边。

2. 存在一个点uuu，满足对于任意的 v∈[1,n]v \in [1,n]v∈[1,n] ，图中都存在边 (u,v)(u,v)(u,v) 和 (v,u)(v,u)(v,u) ，我们称 uuu 是中心点。注意：这意味着 uuu 需要有自环。

3. 除了中心点之外，其它所有点的入度和出度均为2。

此外，你需要保证操作次数尽可能少。

第一行输入两个整数 n,m(2≤n≤500,1≤m≤1000)n,m(2 \le n \le 500,1 \le m \le 1000)n,m(2≤n≤500,1≤m≤1000) ，分别表示原图的点数和边数。

接下来mmm行，每行输入两个整数 ui,vi(1≤ui,vi≤n)u_i,v_i(1\le u_i,v_i \le n)ui​,vi​(1≤ui​,vi​≤n) ，表示从 uiu_iui​ 到 viv_ivi​ 有一条有向边相连。保证输入不含重边。

思路

对于中心点u可以枚举，对于每个中心点计算答案

  • 对于条件2，记录没有和中心点u连边的边数，记为cnt
  • 对于条件3，去掉和中心点u的边之后，等价于n-1个点都需要有一条出边入边，对这n-1个点跑最大匹配即可，那么对于孤立点只需要连向自己即可
  • 那么需要删除的边为m-(和中心点连接的边+最大匹配)
  • 需要添加的边为n-1-最大匹配+没有和中心点u连接的边

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=510;

int mp[N][N];

void solve()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		mp[a][b]++;
	}
	
	ll ans=1e9;
	
	
	auto work=[&](int x)
	{
		int cnt=0;//缺少的边
		for(int i=1;i<=n;i++)
		{
			if(i==x)
			{
				if(!mp[i][x]) cnt++;
				continue;
			}
			if(!mp[i][x]) cnt++;
			if(!mp[x][i]) cnt++;
		}
		
		int res=0;//最大匹配，有用的边
		vector<int>match(n+1),vis(n+1);
		
		
		auto dfs=[&](auto &&dfs,int x,int v)->bool
		{
			for(int i=1;i<=n;i++)
			{
				if(i==v) continue;
				if(vis[i] || !mp[i][x]) continue;
				vis[i]=1;
				
				if(!match[i] || dfs(dfs,match[i],v))
				{
					match[i]=x;
					return true;
				}
			}
			return false;
		};
		for(int i=1;i<=n;i++)
		{
			if(i==x) continue;
			fill(all(vis),0);
			if(dfs(dfs,i,x)) res++;
		}
		//一共有n-1个点需要和中心点连两条边,那么有2*n-1-cnt条有用的
		//m-有用-res 给出的边中没用的,既需要删除的
		ll del=m-(2*n-1-cnt)-res;
		//n-1-res n-1个点需要一出一入，对于不在最大匹配里的和自己连边即可
		ll add=n-1-res;
		
		return del+add+cnt;
		
		
	};
	
	
	
	for(int i=1;i<=n;i++)
	{
		ans=min(ans,work(i));
	}
	cout<<ans<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC 236773插座

题意

Playf刚刚搬完家，他的新家有 mmm 个插座，编号依次为 1,2,...,m1,2,...,m1,2,...,m 。Playf总共有 nnn 个电器，编号依次为 1,2,...,n1,2,...,n1,2,...,n。 出于某些原因，每一个电器只能与特定的插座连接，每个插座只能连接一个电器。具体地，总共有 kkk 种电器和插座的连接方式。此外，Playf还带了一个插线板，这意味着Playf可以把插线板连在某一个插座上，使得这个插座最多能连接3个电器。Playf想知道他最多能让多少个电器成功连到适合的插座上。
第一行输入三个整数 m,n,k(1≤n,m≤1500,0≤k≤75000)m,n,k(1\le n,m \le 1500, 0\le k \le 75000)m,n,k(1≤n,m≤1500,0≤k≤75000) ，分别表示插座个数，电器个数，连接方式总数。

接下来 kkk行，每行两个整数 ui,vi(1≤ui≤m,1≤vi≤n)u_i,v_i(1\le u_i \le m,1 \le v_i \le n)ui​,vi​(1≤ui​≤m,1≤vi​≤n) ，描述一个连接方式，表示编号为 uiu_iui​ 的插座可以被编号为 viv_ivi​ 的电器连接。

思路

回忆二分图最大匹配的算法流程，对每个点不断找增广路，存在增广路则匹配数加1，因此我们可以求出原图的最大匹配之后尝试对每个点进行扩展，建立两个虚点，其连边方式和尝试扩展的点连边方式相同，之后对这两个点找增广路，注意每个点扩展完之后需要恢复到原图的状态

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1510;
vector<int>e[N<<3];

void solve()
{
	ll n,m,k;
	cin>>n>>m>>k;
	
	for(int i=1;i<=k;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	int cnt=0;
	vector<int>vis(m+10);
	vector<int>match(m+10);
	
	auto dfs=[&](auto && dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			
			if(!match[ed] || dfs(dfs,match[ed]))
			{
				match[ed]=u;
				return true;
			}
		}
		return false;
	};
	
	for(int i=1;i<=n;i++)
	{
		fill(all(vis),0);
		if(dfs(dfs,i)) cnt++;
	}
	//cout<<cnt<<endl;
	
	int res=0;
	for(int i=1;i<=n;i++)
	{
		auto match1=match;
		auto e1=e;
		
		int add=0;
		for(auto ed:e[i])
		{
			e1[i+n].pb(ed);
			e1[i+2*n].pb(ed);
		}
		
		auto dfs1=[&](auto &&dfs1,int u)->bool
		{
			for(auto ed:e1[u])
			{
				if(vis[ed]) continue;
				vis[ed]=1;
				
				if(!match1[ed] || dfs1(dfs1,match1[ed]))
				{
					match1[ed]=u;
					return true;
				}
			}
			return false;
		};
		
		fill(all(vis),0);
		if(dfs1(dfs1,i+n)) add++;
		fill(all(vis),0);
		if(dfs1(dfs1,i+2*n)) add++;
		res=max(res,add);
	}
	cout<<cnt+res<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC34649 color

题意

给一个没有重边的二分图,要求给边染色,有公共点的边不能同色，求最少颜色数以及染色方案

思路

最少颜色数一定是度数最多的点，每次从度数最多的点染色，和寻找增广路类似

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1010;
vector<int>e[N];

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<int>x(m+1),y(m+1);
	vector<int>d(n+1);
	
	int mx=-1e9;
	for(int i=1;i<=m;i++)
	{
		cin>>x[i]>>y[i];
		d[x[i]]++;
		d[y[i]]++;
		mx=max({mx,d[x[i]],d[y[i]]});
	}
	
	auto cmp=[&](int x,int y) {return d[x]>d[y];};
	
	vector<int>match(n+1),vis(n+1);
	vector<int>id(n+1);
	vector<vector<int>>color(n+1,vector<int>(n+1));
	
	for(int i=1;i<=n;i++) id[i]=i;
	
	
	auto dfs=[&](auto && dfs,int u)->bool
	{
		for(auto ed:e[u])
		{
			if(vis[ed]) continue;
			vis[ed]=1;
			
			if(!match[ed] || dfs(dfs,match[ed]))
			{
				match[ed]=u;
				match[u]=ed;
				return true;
			}
		}
		return false;
	};
	
	for(int i=1;i<=mx;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!color[x[j]][y[j]])
			{
				e[x[j]].pb(y[j]);
				e[y[j]].pb(x[j]);
			}
		}
		sort(all(id),cmp);
		fill(all(match),0);
		for(int p=1,k=id[p];p<=n;k=id[++p])
		{
			if(!match[k])
			{
				fill(all(vis),0);
				dfs(dfs,k);
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(match[j])
			{
				color[j][match[j]]=i;
				//cout<<j<<" "<<match[i]<<i<<endl;
				d[j]--;
			}
			e[j].clear();
		}
	}
	cout<<mx<<endl;
	for(int i=1;i<=m;i++)
	{
		cout<<color[x[i]][y[i]]<<endl;
	}
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

图的连通性

NC35796A可达性

题意

给出一个 0≤N≤1050 \leq N \leq 1050≤N≤105 点数、0≤M≤1050 \leq M \leq 1050≤M≤105 边数的有向图，
输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。

思路

观察后发现答案为缩点后入度为0的点的集合，缩点后从小到大枚举点，符合条件加入，需要注意同一个连通分量内的点只加入一个即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1e5+10;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed])
		{
			low[x]=min(low[x],dfn[ed]);
		}
	}
	if(dfn[x]==low[x])
	{
		int y;
		++cnt;
		do
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			siz[cnt]++;
		}while(y!=x);
	}
}

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	//cout<<cnt<<endl;
	
	vector<int>d(n+1);
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i])
			{
				d[scc[ed]]++;
			}
		}
	}
	
	set<int>s;
	vector<int>vis(n+1);
	for(int i=1;i<=n;i++)
	{
		if(vis[scc[i]]) continue;
		if(!d[scc[i]]) {s.insert(i);vis[scc[i]]=1;}
	}
	cout<<s.size()<<endl;
	for(auto t:s) cout<<t<<" ";
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796B受欢迎的牛

题意

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。

这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。

你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

思路

画图后发现答案为缩点后出度为0的连通块的大小，因为要保证所有牛都认为这些牛是受欢迎的，所有这样的连通块只能有1个

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1e5+10;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed])
		{
			low[x]=min(low[x],dfn[ed]);
		}
	}
	if(dfn[x]==low[x])
	{
		int y;
		++cnt;
		do
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			siz[cnt]++;
		}while(y!=x);
	}
}

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	//cout<<cnt<<endl;
	
	vector<int>d(n+1);
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i]) d[scc[i]]++;
			
		}
	}
	
	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		if(!d[i])
		{
			if(ans==0) ans=siz[i];
			else {cout<<0<<endl;return;}
		}
	}
	cout<<ans<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796C最大半连通子图

题意

一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意 两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。

若G’=(V’,E’)满足V’∈V，E’是E中所有跟V’有关的边， 则称G’是G的一个导出子图。

若G’是G的导出子图，且G’半连通，则称G’为G的半连通子图。

若G’是G所有半连通子图 中包含节点数最多的，则称G’是G的最大半连通子图。

给定一个有向图G，请求出G的最大半连通子图拥有的节点数K ，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述
接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。
图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。
N ≤ 100000, M ≤ 1000000；对于100%的数据， X ≤ 10^8

思路

发现半连通子图一定是原图缩点后的一条链，那么最大半连通子图即在新图上找一条链，使得链上的强连通分量内的点最多，可以用dp求，因为scc即逆拓扑序所以缩点完之后不需要拓扑排序，直接按scc编号从大到小dp即可，注意建新图的时候要对边去重防止方案数重复计算

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1e5+10;
vector<int>e[N];

int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
vector<int>e1[N];

void tarjan(int x)
{
	low[x]=dfn[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed]) low[x]=min(low[x],dfn[ed]);
	}
	if(low[x]==dfn[x])
	{
		int y;
		cnt++;
		do
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			siz[cnt]++;
		}while(x!=y);
	}
}


void solve()
{
	int n,m,p;
	cin>>n>>m>>p;
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
	}
	
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	
	unordered_set<ll>s;
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			int a=scc[i],b=scc[ed];
			if(a!=b)
			{
				ll h=(ll)a*1000000+b;
				if(!s.count(h))
				{
					e1[a].pb(b);
					s.insert(h);
				}
				
			}
		}
	}
	
	vector<int>dp(cnt+1);//到i时的最大点数
	vector<int>dp1(cnt+1);//到i时的最大方案数
	
	
	for(int i=cnt;i>=1;i--)
	{
		if(!dp[i]) 
		{
			dp[i]=siz[i];
			dp1[i]=1;
		}
		for(auto ed:e1[i])
		{
			if(dp[ed]<dp[i]+siz[ed])
			{
				dp[ed]=dp[i]+siz[ed];
				dp1[ed]=dp1[i];
			}
			else if(dp[ed]==dp[i]+siz[ed])
			{
				dp1[ed]=(dp1[ed]+dp1[i])%p;
			}
		}
	}
	
	int mx=0;
	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		if(dp[i]>mx)
		{
			mx=dp[i];
			ans=dp1[i];
		}
		else if(dp[i]==mx) ans=(ans+dp1[i])%p;
	}
	
	cout<<mx<<endl;
	cout<<ans<<endl;
	
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796D嗅探器

题意

给定一张无向图，求a,b直接编号最小的割点

思路

  • 如何判断x点是否为a，b的割点呢，我们知道若dfn[u]<dfn[v]dfn[u]<dfn[v]dfn[u]<dfn[v]则u不在v的搜索树中，若dfn[u]>dfn[v]dfn[u]>dfn[v]dfn[u]>dfn[v]则v在u的搜索子树内，那么我们只需要判断a,b是否满足一点在x的搜索子树而另一点不在，即
  • $ dfn[x]>dfn[u] && dfn[y]<dfn[u] $
  • $ dfn[y]>dfn[u] && dfn[x]<dfn[u] $

但是还存在一种情况即a,b都在x的搜索子树内，此时满足

  • $ dfn[x]>dfn[u] && dfn[y]<=dfn[u] $

所以最终答案需要满足

  • u是割点
  • v是u割掉的这一支的首节点
  • a或b在v子树内且b或a不在

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=1010;
int low[N],dfn[N],tot;
int ans=1e9;
vector<int>e[N];

int a,b;

bool check(int x)
{
	if(dfn[x]<=dfn[a] && dfn[x]>dfn[b]) return 1;
	if(dfn[x]<=dfn[b] && dfn[x]>dfn[a]) return 1;
	return 0;
}

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
			
			if(low[ed]>=dfn[x] && x!=a && x!=b)
			{
				if(check(ed)) ans=min(ans,x);
			}
		}
		else
		low[x]=min(low[x],dfn[ed]);
	}
}


void solve()
{
	int n;cin>>n;
	
	while(cin>>a>>b)
	{
		if(a==0 && b==0) break;
		e[a].pb(b);
		e[b].pb(a);
	}
	cin>>a>>b;
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	
	
	if(ans==1e9) cout<<"No solution"<<endl;
	else cout<<ans<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796E Network of Schools

题意

有一些学校会向其他学校分享软件，即如果这个学校得到了软件，那么在分享列表中的学校也会得到软件。注意这种关系是单向的，即如果 aaa 在 bbb 的列表中，那么 bbb 不一定在 aaa 的列表中。

现在，你需要向其中一些学校下发新软件。为了节约下发软件的成本，你需要回答以下两个问题。

  1. 至少需要向几个学校下发新软件，可以使得所有学校均获得新软件。
  2. 定义一次扩展为在某个学校的分享列表中增加一个学校。至少需要进行几次扩展，才可以使得无论对哪个学校仅下发一次软件就可以使得所有学校获得新软件。

两个问题相互独立。

思路

对于第一问答案显然为缩点后入度为0的点，入度不为0说明可以靠其他学校下发得到软件
第二问等价为若干个强连通分量，需要添加几条边可以使这些强连通分量变成一个，答案为入度为0点的个数和出度为0点的个数的最大值

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
//#include<stack>
//#include<deque>
//#include<bitset>
//#include<functional>

#define ll long long
#define inf 0x3f3f3f3f
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define pb push_back
using namespace std;

typedef pair<int,int>PII;
const int N=1e4+10;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
int n;
vector<int>e[N];
int din[N],dout[N];
//1.缩点后入度为0的点
//2.入度、出度为0点个数最大值
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		
		else if(instk[ed])
		{
			low[x]=min(low[x],dfn[ed]);
		}
	}
	
	if(dfn[x]==low[x])
	{
		int y;cnt++;
		do
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			++siz[cnt];
		}while(y!=x);
	}
	
}


void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		while(cin>>x,x)
		{
			e[i].pb(x);
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i])//两点不属于一个强连通分量却有出入度关系
			{
				din[scc[ed]]++;//缩点后的点出入度加加
				dout[scc[i]]++;
			}
		}
	}
	
	int a,b;
	a=b=0;//出入度为0点个数
	for(int i=1;i<=cnt;i++)
	{
		if(!din[i]) a++;
		if(!dout[i]) b++;
	}
	cout<<a<<endl;
	if(cnt==1) cout<<0<<endl;//特判一个连通分量
	else cout<<max(a,b)<<endl;
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

Cow Ski Area

题意

约翰的表哥罗恩生活在科罗拉多州。他近来打算教他的奶牛们滑雪，但是奶牛们非常害羞，不敢在游人组织的度假胜地滑雪。没办法，他只好自己建滑雪场了。罗恩的雪场可以划分为 WWW 列 LLL 行 (1≤W≤500,1≤L≤500)(1\le W\le 500, 1\le L\le 500)(1≤W≤500,1≤L≤500)，每个方格有一个特定的高度 H(0≤H≤9999)H(0\le H\le 9999)H(0≤H≤9999)。奶牛可以在相邻方格间滑雪，而且不能由低到高滑。

为了保证任意方格可以互通，罗恩打算造一些直达缆车。缆车很强大，可以连接任意两个方格，而且是双向的。而且同一个方格也可以造多台缆车。但是缆车的建造费用贵得吓人，所以他希望造尽量少的缆车。那最少需要造多少台呢？

思路

将每个格点看成一个点，连边后缩点问题又转化为多个强连通分量加边变成一个的问题

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=500*500+10;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed]) low[x]=min(low[x],dfn[ed]);
	}
	
	if(low[x]==dfn[x])
	{
		int y;
		cnt++;
		do{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			siz[cnt]++;
		}while(y!=x);
	}
}

int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};

void solve()
{
	int n,m;
	cin>>m>>n;
	
	vector<vector<int>>a(n+1,vector<int>(m+1));
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=0;k<4;k++)
			{
				int x=i+dx[k];
				int y=j+dy[k];
				if(x<1 || x>n || y<1 || y>m) continue;
				if(a[x][y]>a[i][j]) continue;
				e[(i-1)*m+j].pb((x-1)*m+y);
			}
		}
	}
	
	for(int i=1;i<=n*m;i++)
	{
		if(!dfn[i]) tarjan(i);
	}
	
	vector<int>din(n*m+1),dout(n*m+1);
	for(int i=1;i<=n*m;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i])
			{
				din[scc[ed]]++;
				dout[scc[i]]++;
			}
		}
	}
	//cout<<cnt<<endl;
	int ans1=0;
	int ans2=0;
	for(int i=1;i<=cnt;i++)
	{
		if(din[i]==0) ans1++;
		if(dout[i]==0) ans2++;
	}
	
	if(cnt==1) cout<<0<<endl;
	else cout<<max(ans1,ans2)<<endl;
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796F Redundant Paths

题意

给定一张无向图，需要添加几条边可以使图是一个边双连通分量，即不存在桥

思路

边双缩点之后，新图是一颗树而且树边都为割边，那么我们对于每一条根节点（度不能为1）到叶子节点(度为1)的链，使其两两相连，每次加边可以消除两条链上的桥，总次数即⌈cnt2⌉\lceil \frac{cnt}{2} \rceil⌈2cnt​⌉,其中cnt为度数为1的点的个数

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=5010;
const int M=10010;
struct edge{
	int to,ne;//终点，下一条边
}e[M];
int h[N];
int idx=1;
int dfn[N],low[N],tot;
stack<int>stk;

int dcc[N],cnt;//边双
int bri[M];//桥
int d[N];

void add(int a,int b)
{
	e[++idx].to=b;
	e[idx].ne=h[a];
	h[a]=idx;
}

void tarjan(int x,int in_edg)
{
	dfn[x]=low[x]=++tot;
	stk.push(x);
	for(int i=h[x];i;i=e[i].ne)
	{
		int y=e[i].to;
		if(!dfn[y])
		{
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]) bri[i]=bri[i^1]=true;
		}
		else if(i!=(in_edg^1)) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])//边双的根
	{
		++cnt;
		while(1)
		{
			int y=stk.top();
			stk.pop();
			dcc[y]=cnt;
			if(y==x) break;
		}
	}
}

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	
	tarjan(1,0);
	
	for(int i=2;i<=idx;i++)
	{
		if(bri[i])//割边
		{
			d[dcc[e[i].to]]++;//割边终点所在边双度数+1
		}
	}
	
	int sum=0;
	//cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++)
	{
		if(d[i]==1) sum++;
	}
	cout<<(sum+1)/2<<endl;
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796H 软件安装

题意

现在我们的手头有 NNN 个软件，对于一个软件 iii，它要占用 WiW_iWi​ 的磁盘空间，它的价值为 ViV_iVi​。我们希望从中选择一些软件安装到一台磁盘容量为 MMM 计算机上，使得这些软件的价值尽可能大（即 ViV_iVi​ 的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件 iii 只有在安装了软件 jjj（包括软件 jjj 的直接或间接依赖）的情况下才能正确工作（软件 iii 依赖软件 jjj)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 000。

我们现在知道了软件之间的依赖关系：软件 iii 依赖软件 DiD_iDi​。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 Di=0D_i=0Di​=0，这时只要这个软件安装了，它就能正常工作。

思路

似乎是树上背包，但是原图并非一颗树，此时我们考虑对于在同一个强连通分量内的点，只能都选，或者都不选，那么完全可以缩点，缩完点之后的图是一个dag，似乎还不是一棵树，但是题目中说明一个软件最多依赖一个软件，即每个点最多有一个父节点，那么缩点之后一定是一颗树，此时跑树上背包即可
需要注意的是防止有孤点，我们可以建立虚拟源点0，将其他入度为0的点都连向0，此时新图为0为根的树

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=110;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed]) low[x]=min(low[x],dfn[ed]);
	}
	if(low[x]==dfn[x])
	{
		int y;++cnt;
		do{
			y=stk[top--];
			instk[y]=0;
			siz[cnt]++;
			scc[y]=cnt;
		}while(y!=x);
	}
}

vector<int>e1[N];


void solve()
{
	int n,m;
	cin>>n>>m;
	vector<int>w(n+1),v(n+1);
	
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) cin>>v[i];
	
	int root=-1;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		if(x==0) root=i;
		else e[x].pb(i);
	}
	
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	
	vector<int>d(cnt+1);
	for(int i=1;i<=n;i++)
	{
		for(auto ed:e[i])
		{
			if(scc[ed]!=scc[i])
			{
				e1[scc[i]].pb(scc[ed]);
				d[scc[ed]]++;
			}
		}
	}
	
	for(int i=1;i<=cnt;i++) if(d[i]==0) e1[0].pb(i);
	
	vector<vector<int>>dp(cnt+1,vector<int>(m+1));
	vector<int>w1(cnt+1),v1(cnt+1);
	for(int i=1;i<=n;i++)
	{
		w1[scc[i]]+=w[i];
		v1[scc[i]]+=v[i];
	}
	
	auto dfs=[&](auto&&dfs,int u,int fa)->void
	{
		for(int i=w1[u];i<=m;i++) dp[u][i]=v1[u];//u必须选
		
		for(auto ed:e1[u])
		{
			if(ed==fa) continue;
			dfs(dfs,ed,u);
			for(int j=m;j>=w1[u];j--)
			{
				for(int k=0;k<=j-w1[u];k++)
				{
					dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[ed][k]);
				}
			}
		}
	};
	dfs(dfs,0,-1);
	cout<<dp[0][m]<<endl;
	
}
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

NC35796I King’s Quest

题意

给出n个男生和n个女生，给出每个男生喜欢的女生，以及一组完备匹配，求保证匹配结果是完美匹配的每个男生可以选择的女生

思路

将每个男生和其喜欢的女生连边，每个女生和初始其要结婚的对象连边(给出的完备匹配),可以发现缩点后在同一个连通块的男生女生是可以互相选择的，那么只要求出缩点之后每个连通块内的点即可

代码

#include<bits/stdc++.h>

#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define i128 __int128

using namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  

const int N=4010;
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

vector<int>e[N];

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	
	for(auto ed:e[x])
	{
		if(!dfn[ed])
		{
			tarjan(ed);
			low[x]=min(low[x],low[ed]);
		}
		else if(instk[ed]) low[x]=min(low[x],dfn[ed]);
	}
	if(low[x]==dfn[x])
	{
		int y;++cnt;
		do{
			y=stk[top--];
			instk[y]=0;
			siz[cnt]++;
			scc[y]=cnt;
		}while(y!=x);
	}
}


void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		int k;cin>>k;
		while(k--)
		{
			int x;cin>>x;
			e[i].pb(x+n);
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		e[x+n].pb(i);
	}
	
	for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
	
	for(int i=1;i<=n;i++)
	{
		vector<int>ans;
		for(auto ed:e[i])
		{
			if(scc[ed]==scc[i]) ans.pb(ed-n);
		}
		sort(all0(ans));
		cout<<ans.size()<<" ";
		for(auto t:ans) cout<<t<<" ";
		cout<<endl;
	}
	
}
	
	
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	solve();
	
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布