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

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條評論
主站蜘蛛池模板: 国产骚b | 99er视频| 免费播放欧美毛片欧美aaaaa | www亚洲视频 | 午夜精品久久久久久久90蜜桃 | 性xxx免费| 国产精品久久久久久免费播放 | 欧美黄色网页 | 干干日日| 欧美成人私人视频88在线观看 | 黑人欧美一级毛片 | 超激情碰碰碰啪在线视频 | 欧美不卡影院 | 久久精品国产清白在天天线 | 亚洲欧美日韩国产综合 | 国产特黄一级毛片特黄 | 精品久久久久久久久久香蕉 | 久久精品视频7 | 露脸真实国产精品自在 | 色老老精品偷偷鲁 | 久久er国产精品免费观看2 | 元龙第三季动漫在线观看免费版 | 91chinese 永久免费 | 久久好看视频 | 午夜在线视频一区二区三区 | 91精品国产色综合久久不卡蜜 | 久久久精品久久久久久久久久久 | 亚洲国产日本 | 日韩福利影院 | 天天操天天干视频 | 香蕉久久夜色精品国产2020 | 992人人草| 久久精品视频亚洲 | 九九视频国产免 | 国产精品久久久精品视频 | 一级做性色a爱片久久片 | 人人澡 人人澡 人人看欧美 | 日本成人二区 | 一级二级三级毛片 | 天天干夜夜爽 | 欧美国产激情二区三区 |