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

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條評論
主站蜘蛛池模板: 亚洲精品久久麻豆蜜桃 | 精品不卡一区中文字幕 | 国产成a人片在线观看视频 国产成a人片在线观看视频99 | 午夜激情婷婷 | 波多野结衣国产一区二区三区 | 999yy成年在线视频免费看 | 深夜福利剧场 | 亚洲成人在线观看视频 | 免费国产一区二区在免费观看 | 久久精品亚洲日本波多野结衣 | 久久草在线看 | 国产护士资源总站 | 亚洲四虎 | 国产三级做爰高清视频a | 黄色录像一级毛片 | 亚洲视频精选 | 在线中文字幕视频 | www黄在线观看| 就要爱综合 | 久久精品国产国产精品四凭 | 日本久操视频 | 欧日韩美香蕉在线观看 | 热久久99精品这里有精品 | 国产精品综合在线 | 精品欧美日韩一区二区三区 | 国产精品免费久久久久影院小说 | 中文字幕日韩欧美 | 97视频免费人人观看人人 | 猫咪www免费人成在线观看网址 | 亚洲爱爱天堂 | 999精品免费视频 | 久久精品国产在热久久2019 | 91精品自在拍精选久久 | 欧美vs日韩vs国产在线观看 | 爱操综合| 乱色 另类图区 | 男人猛躁女人成人免费视频 | 日韩一区二区久久久久久 | 久久久久久久久久免费视频 | 国内精品久久久久影院6 | 男女车车好快的车车免费网站 |