题意: 先给你一个 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]=1;
- for(ll i=head[u];i!=-1;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]]=0;
- index--;
- }
- while(u!=instack[index+1]);
- }
- return;
- }
- void init()
- {
- memset(indeg,0,sizeof(indeg));
- memset(outdeg,0,sizeof(outdeg));
- memset(head,-1,sizeof(head));
- cnt=step=index=scc_cnt=0;
- memset(visit,0,sizeof(visit));
- memset(low,0,sizeof(low));
- memset(dfn,0,sizeof(dfn));
- for(int i=1;i<=n;i++)
- scc[i].clear();
- }
- int main()
- {
- ll t;
- ll cot=0;
- scanf("%lld",&t);
- while(t--)
- {
- cot++;
- scanf("%lld%lld",&n,&m);init();
- for(int i=1;i<=m;i++)
- {
- scanf("%lld%lld",&x[i],&y[i]);
- add(x[i],y[i]);
- }
- for(int i=1;i<=n;i++)
- if(!dfn[i])
- tarjan(i);
- printf("Case %d:",cot);
- if(scc_cnt==1)
- printf("-1\n");
- else
- {
- for(int i=1;i<=m;i++)
- {
- if(sccno[x[i]]==sccno[y[i]])
- continue;
- else
- {
- indeg[sccno[x[i]]]++;outdeg[sccno[y[i]]]++;
- }
- }
- ll tmpans=0;ll ans=0;
- for(int i=1;i<=scc_cnt;i++)
- {
- if(indeg[i]==0||outdeg[i]==0)
- {
- tmpans=0;
- ll tmp=n-scc[i].size();
- tmpans+=(tmp)*(tmp-1);
- tmpans+=(scc[i].size())*(scc[i].size()-1);
- tmpans+=(scc[i].size())*tmp;tmpans-=m;
- ans=max(ans,tmpans);
- }
- }
- printf("%lld\n",ans);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3007934.html