Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

HDU 4635 (完全图 和 有向图缩点)

大头冲锋车丶 2019-08-12 16:47:00 阅读数:24 评论数:0 点赞数:0 收藏数:0

题目链接:HDU  4635

 

题目大意:

 

给你一个有向图,加有向边,使得这个图是简单有向图。问你最多加多少条有向边。

 

简单有向图:

1、不存在有向重边。

2、不存在图循环。(注意是不存在 “图” 循环,就是不能使整个图成为 “强连通图” 。意思是可以存在环,但不能是全图循环。同样,两个点之间可以有两条相反有向边。)

 

分析:

1、如果我要加最多的边,全图仍然不为 “强连通图” 。那么最多的情况就是,有两个巨大的环,他们之前有且仅有一条有向边。故先进行 “有向图缩点” ,先从 小环 开始分析。

2、加边加到最后,一定存在仅剩的两个超级点 X 与 Y ,且 X 与 Y 之间有且仅有一条有向边。这样可以使得 X Y 分处两个最大环。

3、缩点加边到最后,X 与 Y 一定是 X → Y 或者 Y → X 的,所以作为 X Y 的前提条件是, 入度为 0 或者出度为 0 。(重点)

4、其次,X 与 Y 是两个最大有向环,那么我们可以使 X 或 Y 变成完全图,就可以继续加边而且不会导致全图变成 “强连通图” ,因为 X 与 Y 中间始终仅有一条有向边。

5、假设 X Y 之间有 : X → Y ,则我使 X 中的所有节点 ,全部以 → 有向边连接 Y 中的所有节点,也不会使得全图变为 “强连通图” ,故我还可以这样加边。(注意,连的边一定要与 X 到 Y 之间的有向边同向,否则就变成环了)

 

通过以上分析我们可以知道思路:

假设 X 的节点数为 x ,Y 的节点数为 y 。

1、以 X 为完全图时,X 中的有向边数最多为: x * (x - 1)

2、以 Y 为完全图时,Y 中的有向边数最多为: y * (y - 1)

3、X 中的全部节点以同一种有向边连接 Y 的全部节点,边数: x * y

4、由于给了 m 条边,故只需要加 x * (x - 1)+ y * (y - 1)+ x * y - m 条边即可。

 

将上面的 x * (x - 1)+ y * (y - 1)+ x * y - m x + y = n 联立得:

加的边数为:n2 - x * y - n - m 

故我们只需要使 x * y 最小即可。而由于 x + y = n ,是定值,所以 x * y 的最小值即 x 的最小值 乘以 y (y = n - x) 。

由于 X 与 Y 是入度或出度为 0 的点,故只要找出这类缩点后的超级点中,点的个数最小的作为 X 点,X 自身成为完全图,不需要加别的点。然后剩下的所有点与 Y 点一同成为完全图即可。这要就可以保证 x 最小了。

 

代码如下:

 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define maxn 100008
using namespace std;
typedef long long ll;
int cnt, Index, tot, sum;
int head[maxn], low[maxn], dfn[maxn], q[maxn];
int in[maxn],out[maxn];
int qhead[maxn];
bool vis[maxn];
int pre[maxn];
ll ans[maxn],n,m;
struct Edge
{
    int to;
    int next;
}edge[maxn << ];
inline void add(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
    return;
}
inline void tarjan(int u)
{
    low[u] = dfn[u] = ++Index;
    q[++tot] = u;
    vis[u] = true;
    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 (low[u] == dfn[u])
    {       
        ++sum;
        do {
            ans[sum]++;
            pre[q[tot]] = sum;
            vis[q[tot--]] = false;
        } while (q[tot + ] != u);
    }
    return;
}
void init()
{
    cnt=Index=tot=sum=;
    for(int i=;i<=n;i++) dfn[i]=vis[i]=head[i]=qhead[i]=ans[i]=in[i]=out[i]=;
    memset(edge,,sizeof(edge));
    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    int T=;
    while(t--){
        init();
    scanf("%lld%lld", &n, &m);
    int A, B;
    for (int i = ; i <= m; i++) {
        scanf("%d%d", &A, &B);
        add(A, B);
    }
    for (int i = ; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    if(sum==){ printf("Case %d: -1\n",++T ); continue;}
    cnt = ;
    for (int i = ; i <= n; i++) {
        for (int j = head[i]; j; j = edge[j].next) {
            int v = edge[j].to;
            if (pre[i] != pre[v]){
            in[pre[v]]++,out[pre[i]]++;
        }
        }
    }
    ll res=0x3f3f3f3f;
    for(int i=;i<=sum;i++){
        if(in[i]==||out[i]==){
            res=min(res,ans[i]);
        }
    }
    res=1ll*n*n-n-m-res*(n-res);
    printf("Case %d: %lld\n",++T,res );
}
}

 

版权声明
本文为[大头冲锋车丶]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Absofuckinglutely/p/11341083.html