hdu-4635(tarjan缩点)

题意:先给你一个n个点,m条边的有向图,问你最多能够增加多少条边,使得这个图不是一个强连通图

解题思路:考虑最多要添加的边数,所以如果能把初始图划分成两个部分,每个部分都是完全图,这两个部分分别用单向边连接,这样一定是最优的,所以,首先先缩点,因为一个强连通子图的所有点一定要在同一个部分中,缩完点后考虑只有入度和出度为0的点成一个部分才能有最优解,跑所有满足情况的点,当某个点的入度或者出度为0的时候,因为边数最多为两个部分的完全子图+两个部分点的乘积(单向边)-m条给出的边

代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=2e5;
struct Edge
{
ll to;
ll next;
}edge[maxn];
ll low[maxn],dfn[maxn],instack[maxn],sccno[maxn],visit[maxn],head[maxn];
ll scc_cnt,n,m,step,index,cnt;
ll x[maxn],y[maxn];
ll indeg[maxn],outdeg[maxn];
vector<ll>scc[maxn];
bool cnp(int x,int y)
{
return y>x;
}
void add(ll u,ll v)
{
edge[cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt++;
}
void tarjan(ll u)
{
low[u]=dfn[u]=++step;
instack[++index]=u;
visit[u]=;
for(ll i=head[u];i!=-;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[u]=min(low[u],low[edge[i].to]);/*更新儿子节点;*/
}
else if(visit[edge[i].to])
{
low[u]=min(low[u],dfn[edge[i].to]);/*更新回边;*/
}
}
if(low[u]==dfn[u])
{
scc_cnt++;
scc[scc_cnt].clear();
do
{
scc[scc_cnt].push_back(instack[index]);
sccno[instack[index]]=scc_cnt;
visit[instack[index]]=;
index--;
}
while(u!=instack[index+]);
}
return;
}
void init()
{
memset(indeg,,sizeof(indeg));
memset(outdeg,,sizeof(outdeg));
memset(head,-,sizeof(head));
cnt=step=index=scc_cnt=;
memset(visit,,sizeof(visit));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
for(int i=;i<=n;i++)
scc[i].clear();
}
int main()
{
ll t;
ll cot=;
scanf("%lld",&t);
while(t--)
{
cot++;
scanf("%lld%lld",&n,&m);init();
for(int i=;i<=m;i++)
{
scanf("%lld%lld",&x[i],&y[i]);
add(x[i],y[i]);
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
printf("Case %d: ",cot);
if(scc_cnt==)
printf("-1\n");
else
{
for(int i=;i<=m;i++)
{
if(sccno[x[i]]==sccno[y[i]])
continue;
else
{
indeg[sccno[x[i]]]++;outdeg[sccno[y[i]]]++;
}
}
ll tmpans=;ll ans=;
for(int i=;i<=scc_cnt;i++)
{
if(indeg[i]==||outdeg[i]==)
{
tmpans=;
ll tmp=n-scc[i].size();
tmpans+=(tmp)*(tmp-);
tmpans+=(scc[i].size())*(scc[i].size()-);
tmpans+=(scc[i].size())*tmp;tmpans-=m;
ans=max(ans,tmpans);
}
}
printf("%lld\n",ans);
}
}
}
上一篇:sublime安装插件步骤


下一篇:sublime安装插件autoprefixer