HDU 4635 Strongly connected(强连通分量)
http://acm.hdu.edu.cn/showproblem.php?pid=4635
题意:给你一个n个点和m条边的有向图,问你最多添加多少条边能使得该图依然不是强连通的?(若该图初始已经强连通,输出-1)
分析:
一个不能再添任何边的极大非强连通图一定满足下面情况:
该图由x和y两部分构成,其中x是一个完全有向图,y也是一个完全有向图.且图中只有从x的任一节点到y中任一节点的边,并不存在从y到x的任何边. 最后x+y=n.
上面的极大非连通图的边数F=x*(x-1)+y*(y-1)+x*y=n*(n-1)-x*y.我们要让F值最大,必须让x*y最小,由于x+y=n,所以当x与y的差值最大时,x*y必然最小,F值必然最大.用F-m即我们要求的结果.(仔细想想)
那么x部分的点个数到底是多少呢?我们求出原图的所有强连通分量,然后缩点得新DAG图,只有那些入度==0或出度==0的点(所代表的分量)有资格成为x或y部分(仔细想想).我们只需找出最小值即可.
AC代码: (最后结果要用long long输出)
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
int n,m;
vector<int> G[maxn];
stack<int> S;
int dfs_clock, scc_cnt;
int pre[maxn],sccno[maxn],low[maxn];
int num[maxn];//分量的点数目
int out[maxn],in[maxn];
void dfs(int u)
{
pre[u]=low[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v])
low[u]=min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc_cnt++;
num[scc_cnt]=0;
while(true)
{
int x=S.top(); S.pop();
sccno[x]=scc_cnt;
num[scc_cnt]++;
if(x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
memset(pre,0,sizeof(pre));
memset(sccno,0,sizeof(sccno));
for(int i=1;i<=n;i++)
if(!pre[i]) dfs(i);
}
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) G[i].clear();
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
}
find_scc(n);
for(int i=1;i<=scc_cnt;i++) in[i]=out[i]=0;
for(int u=1;u<=n;u++)
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
int x=sccno[u], y=sccno[v];
if(x==y) continue;
in[y]++;
out[x]++;
}
long long ans=0;
int min_v=1e8;
for(int i=1;i<=scc_cnt;i++)if(out[i]==0 || in[i]==0)
min_v=min(min_v,num[i]);
ans=(long long)n*n-n-(long long)min_v*(n-min_v)-m;
printf("Case %d: %d\n",kase, scc_cnt==1?-1:ans);
}
return 0;
}
分享到:
相关推荐
求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类