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

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| 四虎在线永久 | 精品国产一区二区三区四区色 | www.伊人网| 美女黄频免费观看 | 日本黄色录像 | 欧美在线一级片 | 亚洲五月花 | 四虎国产成人永久精品免费 | 成年网站视频在线观看 | 久久99热不卡精品免费观看 | 久久激情综合色丁香 | 香蕉国产在线 | 国产一区二区免费不卡在线播放 | 亚洲国产精品悠悠久久琪琪 | 香港aa三级久久三级不卡 | 久久中文字幕久久久久 | 美女嗯啊| 亚欧乱色视频大全 | 久久国产精品一区二区三区 | 国产一区二区三区四区 | 午夜精品九九九九99蜜桃 | 苗族一级特黄a大片 | 久久精品国产免费一区 | 中文字幕日本一区波多野不卡 | 国产精品香蕉成人网在线观看 | 91中文字幕yellow字幕网 | 亚洲成人毛片 | 黄页成人免费网站 | 婷婷色在线 | 婷婷综合亚洲 | 能免费看黄的网站 | 欧美国一级毛片片aa | 免费一级淫片 | 久艾草国产成人综合在线视频 | 国产区高清 | 第一序列番外篇在哪里看 | 一区二区亚洲视频 | 五月天婷婷免费观看视频在线 |