本文共 2006 字，大约阅读时间需要 6 分钟。

加了一些边后,一定分成了若干个连通分量

如果有大于两个连通分量,那么连通分量间还可以继续加边,不符合

那么记第一个连通分量是$x$部,第二个是$y$部

不可能同时存在$x$到$y$的边和$y$到$x$的边

这样会把两个连通分量合并成一个

所以两个连通分量内部都是完全图,且$x$部所有点连向$y$(反过来也没关系)

边数为$ans=x\ast (x-1)+y\ast (y-1)+xy$

$ans=x^2+y^2-x-y+xy$

$ans=(x+y{)}^2-(x+y)-xy$

由于$x+y=n$,那么$ans=n^2-n-xy$

所以$x$和$y$差值最大时,$ans$最大

$x$部最小的话,那就是一个入度为零或出度为零的点

且内部节点最小,那么就缩点去找就好了~

#include 
   
    using namespace std;const int maxn = 4e5+10;#define int long longstruct edge{
   	int u,to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = (edge){
   u,v,head[u]},head[u] = cnt;}int low[maxn],dfn[maxn],stac[maxn],vis[maxn],top,id,bccn;int out[maxn],in[maxn],bcc[maxn],point[maxn],n,m;void tarjan(int u){
   	dfn[u] = low[u] = ++id, stac[++top] = u, vis[u] = 1;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )		{
   			tarjan(v);			low[u] = min( low[u],low[v] );		}		else if( vis[v] )			low[u] = min( low[u],dfn[v] );	}	if( low[u]==dfn[u] )	{
   		int temp; bccn++;		while( temp=stac[top--] )		{
   			bcc[temp] = bccn;			vis[temp] = 0; point[bccn]++;			if( temp==u )	break;		}	}}signed main(){
   	int t,casenum=0; cin >> t;	while( t-- )	{
   		cin >> n >> m;		for(int i=1;i<=m;i++)		{
   			int l,r; scanf("%lld%lld",&l,&r);			add(l,r);		}		for(int i=1;i<=n;i++)			if( !dfn[i] )	tarjan(i);		for(int i=2;i<=cnt;i++)		{
   			int u = d[i].u, v = d[i].to;			if( bcc[u]!=bcc[v] )	out[bcc[u]]++,in[bcc[v]]++;		}		int minn = 1e9;		for(int i=1;i<=bccn;i++)			if( in[i]==0||out[i]==0 )	minn = min( minn,point[i] );		cout << "Case " << ++casenum << ": ";		if( bccn==1 )			cout << -1 << endl;		else			cout << n*n-n-minn*(n-minn)-m << endl;		bccn = id = top = 0;	cnt = 1;		for(int i=1;i<=n;i++)			point[i] = bcc[i] = in[i] = low[i] = dfn[i] = head[i] = out[i] = 0;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109677069 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！