概述「DAG加邊至強連通」模型&&luoguP2746校園網Network of Schools

来源:https://www.cnblogs.com/antiquality/archive/2018/07/08/9281211.html
-Advertisement-
Play Games

模型概述 有一DAG,問最少加多少條邊能夠使圖強連通。 題目描述 一些學校連入一個電腦網路。那些學校已訂立了協議:每個學校都會給其它的一些學校分發軟體(稱作“接受學校”)。註意即使 B 在 A 學校的分發列表中, A 也不一定在 B 學校的列表中。 你要寫一個程式計算,根據協議,為了讓網路中所有的學 ...


模型概述

有一DAG,問最少加多少條邊能夠使圖強連通。

題目描述

一些學校連入一個電腦網路。那些學校已訂立了協議:每個學校都會給其它的一些學校分發軟體(稱作“接受學校”)。註意即使 B 在 A 學校的分發列表中, A 也不一定在 B 學校的列表中。

你要寫一個程式計算,根據協議,為了讓網路中所有的學校都用上新軟體,必須接受新軟體副本的最少學校數目(子任務 A)。更進一步,我們想要確定通過給任意一個學校發送新軟體,這個軟體就會分發到網路中的所有學校。為了完成這個任務,我們可能必須擴展接收學校列表,使其加入新成員。計算最少需要增加幾個擴展,使得不論我們給哪個學校發送新軟體,它都會到達其餘所有的學校(子任務 B)。一個擴展就是在一個學校的接收學校列表中引入一個新成員。

輸入輸出格式

輸入格式:

輸入文件的第一行包括一個整數 N:網路中的學校數目(2 <= N <= 100)。學校用前 N 個正整數標識。

接下來 N 行中每行都表示一個接收學校列表(分發列表)。第 i+1 行包括學校 i 的接收學校的標識符。每個列表用 0 結束。空列表只用一個 0 表示。

輸出格式:

你的程式應該在輸出文件中輸出兩行。

第一行應該包括一個正整數:子任務 A 的解。

第二行應該包括子任務 B 的解。


 

題目分析

第一問非常簡單,就是縮點之後求入度為零的點個數。

至於第二問……一開始我想了很久,後來發現好像想複雜去了。

先加邊再刪邊

我一開始想到的是類似於floyd的想法,來試圖刪去“多餘的邊”。

這裡對於多餘的邊的定義是:刪去這些邊後不會改變圖中兩兩點對的連通性。

那麼對於點$x$,將它與所有不能到達的點$y$連邊,最後再考慮哪些邊是可刪去的多餘邊。

但是這樣很冗餘,同時計算出的答案是會偏大的……而且我後來發現好像floyd做不到這個操作?

從圖的性質考慮

先不來考慮森林(其實森林的情況也一樣)比如說這樣一張圖:

標紅的是入度為零的點;標藍的是出度為零的點。

按照之前的想法,那就是把點1,2,3,4與其他所有它們不能到達的點相連。

但是可以發現對於點5,6來說,是能夠到達所有點的;對於點2來說,它只能夠到達自身;並且,所有點都能夠到達點2。

那麼只需要給點2向點5,6連邊,就能夠使圖成為強連通。

更為普遍的情況則是,紅點有$x$個;藍點有$y$個,則最少加邊數為$max\{x,y\}$。

 1 #include<bits/stdc++.h>
 2 const int maxn = 103;
 3 const int maxm = 20003;
 4 
 5 int tim,dfn[maxn],low[maxn],degOut[maxn],degInn[maxn];
 6 int stk[maxn],cnt;
 7 int col[maxn],cols;
 8 int edgeTot,edges[maxm],nxt[maxm],head[maxn];
 9 int n,ans;
10 
11 int read()
12 {
13     char ch = getchar();
14     int num = 0;
15     bool fl = 0;
16     for (; !isdigit(ch); ch = getchar())
17         if (ch=='-') fl = 1;
18     for (; isdigit(ch); ch = getchar())
19         num = (num<<1)+(num<<3)+ch-48;
20     if (fl) num = -num;
21     return num;
22 }
23 void addedge(int u, int v)
24 {
25     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
26 }
27 void tarjan(int x)
28 {
29     dfn[x] = low[x] = ++tim;
30     stk[++cnt] = x;
31     for (int i=head[x]; i!=-1; i=nxt[i])
32     {
33         int v = edges[i];
34         if (!dfn[v])
35             tarjan(v),
36             low[x] = std::min(low[x], low[v]);
37         else if (!col[v])
38             low[x] = std::min(low[x], dfn[v]);
39     }
40     if (low[x]==dfn[x]){
41         col[x] = ++cols;
42         for (; stk[cnt]!=x; cnt--)
43             col[stk[cnt]] = cols;
44         cnt--;
45     }
46 }
47 int main()
48 {
49     memset(head, -1, sizeof head);
50     n = read();
51     for (int i=1; i<=n; i++)
52     {
53         int x;
54         while (x = read())
55             addedge(i, x);
56     }
57     for (int i=1; i<=n; i++)
58         if (!dfn[i]) tarjan(i);
59     for (int i=1; i<=n; i++)
60         for (int j=head[i]; j!=-1; j=nxt[j])
61             if (col[i]!=col[edges[j]])
62                 degInn[col[i]]++, degOut[col[edges[j]]]++;
63     for (int i=1; i<=cols; i++)
64         if (!degOut[i]) ans++;
65     printf("%d\n",ans);
66     if (cols==1) printf("0\n");
67     else{
68         int cnta = 0, cntb = 0;
69         for (int i=1; i<=cols; i++)
70         {
71             if (degInn[i]==0) cnta++;
72             if (degOut[i]==0) cntb++;
73         }
74         printf("%d\n",std::max(cnta, cntb));
75     }
76     return 0;
77 }

 

 

END

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.頭文件 <!DOCTYPE configuration PUBLIC "-//mybatis.org//DTD Config 3.0//EN" "http://mybatis.org/dtd/mybatis-3-config.dtd"> DTD聲明始終以!DOCTYPE開頭 configurat ...
  • 1. 通常防止爬蟲被反主要有以下幾個策略 (1)動態設置User Agent(隨機切換User Agent,模擬不同的瀏覽器) 方法1: 修改setting.py中的User Agent 方法2: 修改setting中的 DEFAULT_REQUEST_HEADERS 方法3 : 在代碼中修改 (2 ...
  • 往列表裡存放數據先進後出(左進) lpush names A B C D E 往列表裡存放數據後進先出(右進) rpush names G P H K 查看列表裡面的數據: lrange names 0(從0開始) -1 切片: lrange names start end(start end 代表 ...
  • 命令: hset info namehgetall infohkeys infohvlls info m系列批量處理: hmset info2 k1 v1 k2 v2 hmget info2 k1 k2 hlen獲取有幾個key hlen info2 hexists判斷是否存在: hexists i ...
  • 本文關鍵詞: java集合框架 框架設計理念 容器 繼承層級結構 繼承圖 集合框架中的抽象類 主要的實現類 實現類特性 集合框架分類 集合框架併發包 併發實現類 什麼是容器? 由一個或多個確定的元素所構成的整體叫做集合。 容器用來包裝或裝載物品的貯存器 (如箱、罐、壇)或者成形或柔軟不成形的包覆材料 ...
  • Flask的g對象 g可以可以看作是單詞global的縮寫,使用“from flask import g”導入,g對象的作用是保存一些在一次請求中多個地方的都需要用到的數據,這些數據可能在用到的時候都需要去進行判斷或其他處理之後才能獲得,如果在第一次獲取的時候就存放到g對象中,就可以避免一些不必要的 ...
  • 中午吃飯時看了一下陸毅版的《三國》,剛好看的是蜀軍缺糧,諸葛亮讓王平去劫司馬懿的糧。司馬懿看蜀軍用木牛流馬運量很方便,就搶了蜀軍的木牛流馬仿製了一批,結果司馬懿用它運糧時,被王平冒充司馬懿的人在驗糧時,對木牛流馬動了手腳,結果木牛流馬不能動彈了,被蜀軍把幾十萬擔的糧食搶走了。看到這裡的時候,我想到了 ...
  • 下麵是EXE代碼 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...