<题目链接>
题目大意：
给你一张有向图，问在保证该图不能成为强连通图的条件下，最多能够添加几条有向边。
解题分析：
我们从反面思考，在该图是一张有向完全图的情况下，最少删去几条边能够使其不是强连通图。即，开始的时候，图的总边树为 n*(n-1)，减去m条已有的边。然后把原图中所有的强连通块进行缩点，对于缩好的点，我们把其分成两部分，保证这两部分点不能够相互可达(即这两部分不是强连通)，所以我们要减去一个部分到另一部分的所有同一方向的边，比如将连通块1到连通块2的所有边都删除，这样，这两部分点就不强连通，整张图也不是强连通图。那如何使删除的边最小呢？因为删除的边为cnt*(n-cnt)，根据简单的数学常识，必然是cnt和(n-cnt)差值最大的时候，他们的乘积最小，所以我们只要记录所有连通块中点数最少的数量即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long ll;
const int N = ;
const int INF = 0x3f3f3f3f; struct Edge{
int to,next;
}edge[N<<]; ll n,m,cnt,head[N];
ll tot,top,atype;
ll dfn[N],low[N],vis[N],stack[N],belong[N],indeg[N],outdeg[N],sum[N];
void init(){
cnt=,tot=,top=,atype=;;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(belong,,sizeof(belong));
memset(indeg,,sizeof(indeg));
memset(outdeg,,sizeof(outdeg));
memset(sum,,sizeof(sum));
}
void addedge(int u,int v){
edge[++cnt].to=v,edge[cnt].next=head[u];
head[u]=cnt;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
stack[top++]=u;
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[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(dfn[u]==low[u]){
atype++;
int v;
do{
v=stack[--top];
belong[v]=atype; //将该强连通块缩点染色
sum[atype]++; //统计该强连通块的点的数量
vis[v]=;
}while(u!=v);
}
} int main(){
int t,cases=;
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&m);
init();
for(int i=;i<m;i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);
}
for(int i=;i<=n;i++)
if(!dfn[i])Tarjan(i);
if(atype==){
printf("Case %d: -1\n",++cases);
continue;
}
for(int u=;u<=n;u++)
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(belong[u]!=belong[v]){ //统计每个连通块的初度和入度
outdeg[belong[u]]++;
indeg[belong[v]]++;
}
}
ll ans=,cnt=INF;
for(int i=;i<=atype;i++)
if(indeg[i]==||outdeg[i]==) //更新初度和入读为0的联通块的数量最小值,因为只需删除一个方向的边
cnt=min(cnt,sum[i]);
ans=n*(n-)-m-cnt*(n-cnt); //n*(n-1)为有向完全图的所有边，m为原图已有的边，cnt*(n-cnt)为分成两部分后删除一个方向的边
printf("Case %d: %lld\n",++cases,ans);
}
return ;
}
2018-11-08