亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 4635 Strongly connected(強連通+縮點)

系統 1621 0

n個點,m條邊的有向圖,求最多能增加多少條邊,原圖任然不是強連通圖。

將問題轉化為,n個點的完全圖,共有n*(n-1)條邊,除去原有的m條邊,最少刪多少條邊,使得該圖不是強連通圖?

求出scc后縮點得到scc圖,對于一個scc點,如果他的入度為0,那么只需在完全圖中,刪去所有指向該強連通分量的邊就行了,對于出度為0的scc點也是如此。而要求最大的可加邊數,只需求出入度或者出度為0的點權最小的那個scc就行,答案便是n*(n-1) - m - sum[_scc] * (n-sum[_scc]) 。

?

    #include<iostream>

#include<algorithm>

#include<vector>

#include<string>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<fstream>

#include<sstream>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define LL long long

#define PB push_back

#define debug puts("**debug**")

using namespace std;



const int maxn = 100001;

int n, m, u, v;

int pre[maxn], low[maxn], dfs_clock, scc_cnt, sccno[maxn], in[maxn], out[maxn],  sum[maxn];

vector<int> G[maxn];

stack<int> S;



void dfs(int u)

{

    pre[u] = low[u] = ++dfs_clock;

    S.push(u);

    REP(i, G[u].size())

    {

        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++;

        for(;;)

        {

            int x = S.top(); S.pop();

            sccno[x] = scc_cnt;

            if(x == u) break;

        }

    }

}



void find_scc()

{

    dfs_clock = scc_cnt = 0;

    CLR(pre, 0); CLR(sccno, 0); CLR(in, 0); CLR(out, 0); CLR(sum, 0);

    FF(i, 1, n+1) if(!pre[i]) dfs(i);

}



int main()

{

    int T; scanf("%d", &T);

    FF(kase, 1, T+1)

    {

        scanf("%d%d", &n, &m);

        FF(i, 1, n+1) G[i].clear();

        REP(i, m)

        {

            scanf("%d%d", &u, &v);

            G[u].PB(v);

        }

        find_scc();

        printf("Case %d: ", kase);

        if(scc_cnt == 1)

        {

            puts("-1");

            continue;

        }

        LL ans = n*(n-1) - m;

        FF(u, 1, n+1)

        {

            sum[sccno[u]]++;

            REP(i, G[u].size())

            {

                int v = G[u][i];

                if(sccno[u] != sccno[v]) out[sccno[u]]++, in[sccno[v]]++;

            }

        }

        int tmp = 1e9;

        FF(i, 1, scc_cnt+1)

            if(in[i] == 0 || out[i] == 0) tmp = min(tmp, sum[i]);

        ans -= tmp*(n-tmp);

        printf("%lld\n", ans);

    }

    return 0;

}
  


?

?

hdu 4635 Strongly connected(強連通+縮點)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国四虎影永久 | 久久精品免费观看视频 | 99久久精品国产自免费 | 国产99视频精品免视看9 | 欧美在线视频免费看 | 国产精品亚洲精品一区二区三区 | 婷婷日韩 | 国内精品视频一区二区三区八戒 | a视频网站 | 国产一级毛片视频在线! | 久久综合久美利坚合众国 | 五月天丁香六月欧美综合 | 久久影院一区 | 日本欧美一区二区三区在线观看 | 亚洲区一二三四区2021 | 2022久久国产精品免费热麻豆 | 日本一级~片免费永久 | 久久久精品2018免费观看 | 亚洲成人网在线观看 | 毛片网站在线 | 四虎色影院 | 婷婷综合久久中文字幕 | 亚洲成在人天堂一区二区 | 久久99九九99九九精品 | 亚洲精品久久久久久久777 | 中文字幕一区久久久久 | 亚洲精品国产男人的天堂 | 久久爱综合久久爱com | 久久精品在现线观看免费15 | 香蕉在线精品亚洲第一区 | 性生活免费视频网站 | 操操网站 | 欧美成人爽毛片在线视频 | 欧美一级毛片高清毛片 | 久久久久九九 | 四虎成人永久地址 | 性xxx欧美 | 久青草国产在视频在线观看 | 美国美女一级毛片免费全 | 非常色的视频 | 久久亚洲精品一区二区三区浴池 |